The Node and the Tree

The node is the binary tree node from the tree chapter, now a private nested class inside the tree:

public class BinarySearchTree<T extends Comparable<T>> {
  private Node<T> root;

  private static class Node<T> {
    T value;
    Node<T> left;
    Node<T> right;

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

A missing child is still null, which stands for the empty tree.

The new part is the bound T extends Comparable<T>. The tree has to compare values to decide whether a value goes left or right. The bound comes from the generics chapter. It guarantees that every T has a compareTo method.

In the tree chapter, every operation was a static method that took a loose Node. Here the tree is a wrapper class, BinarySearchTree. We made the same move in the linked list chapter. There, the LinkedList class owned head, tail, and size and kept them consistent. That is encapsulation. The class also hid the ListItem objects from clients. That is information hiding.

The BinarySearchTree class owns root. Adding to an empty tree creates a new root, and removing the root may replace it, so the class updates that reference itself instead of handing a new root back to the client. The class keeps Node private, so clients never handle nodes. The class also keeps the ordering property as its invariant. This has to be the class’s job, because a single node does not know whether all the values in its subtrees satisfy the ordering property.

As noted, an empty tree is a tree whose root is null:

public BinarySearchTree() {
  root = null;
}

Search, add, and remove have the same structure. The public method belongs to the tree and starts at root. A private helper does the recursive work on a Node, carrying the current node as we move down the tree. This is the public-method/private-helper pattern from recursive binary search.