From a Definition to a Node

We have defined the binary tree on paper: the empty tree, or a node holding a value with a left binary tree and a right binary tree. Let’s translate that definition into code:

public class Node<T> {
  public T value;
  public Node<T> left;
  public Node<T> right;

  public Node(T value) {
    this.value = value;
  }
}

You can see the recursive definition in the fields: left and right each hold a smaller binary tree, and null is the empty tree.

Here is the binary tree from the previous section:

       ╭───╮
       │ 3 │
       ╰─┬─╯
    ┌────┴────┐
  ╭─┴─╮     ╭─┴─╮
  │ 5 │     │ 8 │
  ╰─┬─╯     ╰───╯
  ┌─┘
╭─┴─╮
│ 1 │
╰───╯

Here is how we build it:

Node<Integer> root = new Node<>(3);
Node<Integer> five = new Node<>(5);
Node<Integer> eight = new Node<>(8);
Node<Integer> one = new Node<>(1);

root.left = five;
root.right = eight;
five.left = one;

We never set five.right, or either reference of eight and one, so they stay null. Those are the missing children in the drawing. Every leaf is a node whose two references are both null.

For now, we will work with the node directly. That is what we did with ListItem before the linked-list chapter wrapped it in a class. Like ListItem, the class, its fields, and its constructor are public, so code outside the class can create nodes and link them. Each operation we write will be a method that takes the root of a tree, a single Node, and works downward from there.

Those operations will be recursive, because a binary tree is defined recursively.