Trees and Binary Search Trees

A tree is nodes connected in a hierarchy: one root, every other node with exactly one parent, no cycles. A binary tree gives each node at most two children. A binary search tree adds one invariant that makes it useful.

Vocabulary

That last one is why tree code is naturally recursive: every child is the root of a smaller tree, so almost every method is "handle this node, recurse on both children".

The BST invariant

Every node's left subtree holds smaller keys, its right subtree larger ones. Not just its immediate children — the entire subtree.

    public boolean contains(int value) {
        Node current = root;
        while (current != null) {
            if (value == current.value) {
                return true;
            }
            current = value < current.value ? current.left : current.right;
        }
        return false;
    }

Each comparison discards an entire subtree. On a balanced tree that halves the remaining nodes, so search is O(log n) — the same bargain as binary search, but on a structure that supports cheap insertion.

⚠️ Only while it stays balanced

Insert 1, 2, 3, 4, 5 in order and every node hangs off the right of the previous one. You have a linked list wearing a tree costume, and every operation is O(n).

        // The degenerate case, stated as a measurement rather than a warning.
        BinarySearchTree degenerate = new BinarySearchTree();
        for (int i = 1; i <= 10; i++) {
            degenerate.insert(i);
        }
        Check.eq(degenerate.height(), 10, "sorted input degenerates to a linked list");
        Check.eq(degenerate.inOrder().toString(), "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]", "still correct, just slow");

Ten nodes, height ten, where a balanced tree of ten nodes has height four. Still perfectly correct — just with none of the speed the structure exists for. And sorted input is, again, exactly what real data looks like.

The fix is a self-balancing tree, which rotates nodes on insert to keep the height at O(log n). AVL trees are strictly balanced; red-black trees are looser and cheaper to maintain, which is why TreeMap and TreeSet are red-black trees. This implementation deliberately does not rebalance, so the degenerate case stays visible.

The four traversals

Three are depth-first and differ only in when the node is visited relative to its children.

In-order — left, node, right. On a BST this comes out sorted, which is the whole trick:

    private void inOrder(Node node, List<Integer> out) {
        if (node == null) {
            return;
        }
        inOrder(node.left, out);
        out.add(node.value);
        inOrder(node.right, out);
    }

Pre-order — node, left, right. Visits a parent before its children, so it is what you use to copy or serialise a tree: replaying the sequence rebuilds the same shape.

Post-order — left, right, node. Visits children before their parent, so it is what you use to free a tree or compute anything bottom-up, like the height calculation below.

    private int height(Node node) {
        return node == null ? 0 : 1 + Math.max(height(node.left), height(node.right));
    }

All three are the same three lines in a different order, and their outputs are asserted so the distinction is concrete rather than a diagram:

        Check.eq(tree.inOrder().toString(), "[20, 30, 40, 50, 60, 70, 80]", "in-order is sorted");
        Check.eq(tree.preOrder().toString(), "[50, 30, 20, 40, 70, 60, 80]", "pre-order");
        Check.eq(tree.postOrder().toString(), "[20, 40, 30, 60, 80, 70, 50]", "post-order");

The fourth one is different

        Deque<Node> queue = new ArrayDeque<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            Node node = queue.remove();
            out.add(node.value);
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }

Level order visits every node at depth 1, then depth 2, and so on. It cannot be written recursively — there is no recursive formulation of "visit everything one level down" — so it needs an explicit queue.

That pairing is the thing to carry away: queue for breadth, stack for depth, and recursion is a stack. It is the same fact that makes BFS and DFS the same algorithm with different containers.

Deletion — the case everyone skips

Insert and search are easy. Delete has three cases:

        } else if (node.left == null) {
            size--;
            return node.right;
        } else if (node.right == null) {
            size--;
            return node.left;
        } else {
            // Two children. Replace this node's value with its in-order successor - the smallest
            // value in the right subtree - then delete that successor from the right subtree.
            // The successor has no left child by construction, so that second delete always hits
            // one of the easy cases above and decrements size exactly once.
            Node successor = node.right;
            while (successor.left != null) {
                successor = successor.left;
            }
            node.value = successor.value;
            node.right = delete(node.right, successor.value);
        }

1. No children — return null, and the parent's reference drops it.
2. One child — return that child; it takes the node's place.
3. Two children — this is the interesting one.

With two children you cannot simply remove the node; something has to take its place, and it must preserve the invariant. The only two candidates are the in-order successor (smallest value in the right subtree) and the in-order predecessor (largest in the left). Copy its value up, then delete it — and because it is the leftmost node of that subtree it has no left child, so that second deletion is always case 1 or 2. The recursion terminates by construction.

        tree.delete(20);                       // leaf
        tree.delete(30);                       // one child
        tree.delete(70);                       // two children
        Check.eq(tree.inOrder().toString(), "[40, 50, 60, 80]", "delete a node with two children");

Trees in Java

Choose TreeMap over HashMap when you need order — firstKey, floorKey, headMap, or iteration in sorted order. You pay O(log n) instead of O(1) for it.

What to remember

• The BST invariant covers whole subtrees, not just immediate children.
• O(log n) only while balanced; sorted input makes it a linked list at O(n).
• In-order on a BST is sorted output.
• Pre-order to copy, post-order to fold or free, level order for breadth.
• Deleting a node with two children means promoting its in-order successor.
• Use TreeMap for real work — it rebalances, this one does not.