A tree is a data structure in which each node contains links to zero or more child nodes, but only zero or one parent nodes. Furthermore, in any tree, there should be only one node with zero parents. We refer to the parent-less node as the ‘root’ of the tree. Nodes without children are called ‘leaf nodes’ or simply ‘leaves.’

A binary tree is a tree in which a node may have only zero, one or two children.

Limiting the number of child nodes to two allows us to store data for more efficient searching later, especially if we are careful about how we insert new nodes into the tree.

Much like with the linked list, we define a node class which stores the data and the relationship between each node and its children:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
class KNode { private T value; private KNode left; private KNode right; public KNode(T data) { this.value = data; } public T getValue() { return value; } public void setValue(T data) { this.value = data; } public KNode getLeft() { return this.left; } public KNode getRight() { return this.right; } public void setLeft(KNode newLeft) {this.left = newLeft; } public void setRight(KNode newRight) {this.right = newRight; } } |

In fact, it’s safe to think of the node as being a tree in and of itself: instead of nodes with left and right child nodes, we could speak of trees with left and right subtrees. We could put everything for the entire binary tree concept in a single class, and it wouldn’t be that hard to understand. That’s not possible for all data structures, and I’d like to keep my conventions similar across this entire project, so I’m going to stick with the node/structure class distinction.

Since the node itself contains the bare minimum functionality for the tree, the bare minimum tree class is somewhat spartan.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
public class KBinaryTree { public KNode root; public KBinaryTree(T rootData) { this.root = new KNode(rootData); } public KBinaryTree(KNode root) { this.root = root; } public void printInOrder() { if(this.root != null) { this.printInOrder(this.root); } } public void printInOrder(KNode node) { if(node.getLeft() != null) { this.printInOrder(node.getLeft()); } System.out.print(node + ", "); if(node.getRight() != null) { this.printInOrder(node.getRight()); } } } |

And let’s round things out with some client code.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
public class BinaryTreeTester { public static void main(String[] args) { KBinaryTree tree = new KBinaryTree("root"); tree.root.setLeft("left child"); tree.root.setRight("right child"); tree.root.getLeft().setLeft("leftleft grandchild"); tree.root.getLeft().setRight("leftright grandchild"); tree.root.getRight().setLeft("rightleft grandchild"); tree.root.getRight().setRight("rightright grandchild"); tree.printInOrder(); } } |

Which gives the expected output:

1 |
leftleft grandchild, left child, leftright grandchild, root, rightleft grandchild, right child, rightright grandchild, |

Implementing just a binary tree as such is a little bit silly. The real advantages of the structure become clear with binary search trees, in which we add the restriction that a node’s left child (and their left children) should have values less than the node itself, and that the right children (and their right children) should have values greater than the node itself. This restriction allows us to search the tree very quickly.