A Binary Tree in Java

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 tree

A tree

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

A binary tree 

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:

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.

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

Which gives the expected output:

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.