Binary search trees

Written Explanation

The BST rule

A binary search tree is a binary tree in which, for every node:

• all values in its left subtree are smaller than the node's value, and
• all values in its right subtree are larger than the node's value.

The rule is about the whole subtree, not just the immediate children. In the tree below, 6 is smaller than 8 and sits in 8's left subtree, so it is allowed even though 6 is the right child of 3.

        8
       / \
      3   10
     / \    \
    1   6    14

What about equal values? Books differ: some put duplicates on the left, some on the right. In this lesson we keep each value at most once: inserting a value that is already present does nothing. That is also how a Set behaves.

Search

To look for a value v, start at the root and repeat:

1. If the node is null, the value is not in the tree.
2. If v equals the node's value, you found it.
3. If v is smaller, continue in the left subtree. If larger, continue in the right subtree.

Every comparison eliminates one whole side. This is why the structure is called a search tree. In Java, using the same recursive pattern as Lesson 1:

private boolean contains(Node n, int v) {
    if (n == null) return false;                 // base case: fell off the tree
    if (v == n.value) return true;
    return v < n.value ? contains(n.left, v) : contains(n.right, v);
}

The null check comes first. Without it, a failed search reaches a missing child, and the next line reads n.value on null.

Insert

Insertion is a search that ends by attaching a new node. You search for the place where the value would be, and when you reach null, you put the new node there. Every new value becomes a leaf, and existing nodes never move.

private Node insert(Node n, int v) {
    if (n == null) return new Node(v);          // found the empty spot
    if (v < n.value) n.left = insert(n.left, v);
    else if (v > n.value) n.right = insert(n.right, v);
    // equal: already present, do nothing
    return n;
}

Each recursive call returns the root of the (possibly changed) subtree, and the caller stores it back: n.left = insert(n.left, v). When the subtree did not change, the same node comes back and the assignment changes nothing. When n.left was null, the new node is returned and gets attached. The public method starts the process with root = insert(root, v), which also handles the very first insert into an empty tree.

Cost: one level per step

Each step of search or insert moves one level down, so the number of steps is at most the height of the tree plus one. If the tree is balanced, with its nodes spread out, the height is about log base 2 of n. Doubling the number of values adds only one more level. A balanced tree of about a million nodes needs roughly 20 comparisons at the most. That is the O(log n) you learned in the Big O module.

The word "if" matters. The shape depends on the order of insertion, and a bad order produces a tall tree and slow searches. Lesson 4 shows how. For this lesson, remember that the cost of a BST operation is proportional to its height.

Finding the smallest value

The smallest value is reached by always going left until there is no left child. The largest is found by always going right. This uses the BST rule directly, and it is a loop, not a recursion:

public Integer min() {
    if (root == null) return null;
    Node n = root;
    while (n.left != null) n = n.left;
    return n.value;
}

It returns Integer rather than int so that null can mean "the tree is empty".