Binary Search Trees

A hash table gives expected $O(1)$ lookups but throws away order: it cannot tell you the smallest key, the next key after a given one, or every key in a range. A binary search tree (BST) keeps those queries fast by storing keys in a shape that records their order. Each node holds a key and pointers to a left child, a right child, and a parent; the keys are arranged so that the tree itself is a kind of decision diagram for searching. The result is a dynamic ordered dictionary supporting search, insert, delete, minimum, maximum, predecessor, successor, and in-order traversal, every one of them in time proportional to the tree's height.

The binary search tree property

The arrangement is governed by one local invariant, checked at every node $x$:

Smaller keys live to the left, larger keys to the right, everywhere, not just between a node and its immediate children.¹ This recursive constraint is exactly what lets a search discard half the tree at each step.

Reading this tree: the root is $6$; everything in its left subtree ($\left\{2,3,5\right\}$) is $\le 6$ and everything in its right subtree ($\left\{7,8,9\right\}$) is $\ge 6$, and the same holds recursively at $3$ and $8$.

Searching

To search for a key $k$, start at the root and walk down. At each node, if $k$ equals the node's key we are done; if $k$ is smaller we go left, otherwise we go right. Each comparison drops us one level, so the search traces a single root-to-leaf path.

The procedure is correct by the BST property: when $k<key(x)$, the property guarantees $k$ cannot be in $x$'s right subtree, so discarding it loses nothing. The search visits one node per level and runs in $O(h)$ time, where $h$ is the height of the tree.²

$\text{Tree-Minimum}$ and $\text{Tree-Maximum}$ are the degenerate cases of search: follow left pointers until they run out to reach the smallest key, or right pointers for the largest.

Inserting

Insertion reuses the search path. To insert key $k$, walk down as if searching for it; when the walk falls off the bottom of the tree (reaches a nil child), that empty spot is exactly where $k$ belongs, preserving the BST property. We attach a new leaf there, remembering the parent so we can hook it in.

Like search, insertion walks one root-to-leaf path and costs $O(h)$. New keys always enter as leaves, which is what keeps insertion simple, but also what sets up the trouble we meet below.

Finding a successor

The successor of a node $x$ is the node with the smallest key greater than $key(x)$, the next key in sorted order. There are two cases, and neither needs a comparison of keys, only structure:

• If $x$ has a right subtree, the successor is the minimum of that subtree: the smallest key still larger than $key(x)$.
• If $x$ has no right subtree, the successor is the lowest ancestor whose left child is also an ancestor of $x$; we climb up until we move up a left link.

Both cases follow a single vertical path, down into the right subtree or up through ancestors, so $\text{Tree-Successor}$ also runs in $O(h)$. Predecessor is the mirror image (left subtree's maximum, or climb until a right link).

Deleting a node

Deletion is the one operation that needs care, because removing an internal node leaves a hole that must be filled without disturbing the BST property. There are three cases, in increasing difficulty:

1. $z$ has no children: just detach it from its parent.
2. $z$ has one child: splice that child into $z$'s position.
3. $z$ has two children: $z$'s successor $y$ is the minimum of its right subtree, so $y$ has no left child. Move $y$ into $z$'s position; if $y$ was not $z$'s direct child, first replace $y$ by its own right child.

All three reduce to a single primitive, $\text{Transplant}$, which replaces the subtree rooted at $u$ with the subtree rooted at $v$:

The two-child case is the subtle one. Replacing $z$ by its successor keeps every key in $z$'s left subtree below the new root and every key in the right subtree above it, so the ordering survives:

Each branch does a constant amount of pointer surgery plus at most one $\text{Tree-Minimum}$ call, so $\text{Tree-Delete}$ runs in $O(h)$ like the rest.

The order is already there: inorder walk

Because the BST property sorts keys left-to-right at every node, visiting the tree in order — left subtree, then the node, then right subtree — emits the keys in increasing order.³

The walk visits each of $n$ nodes once, so it runs in $\Theta (n)$ time. This gives a clean way to read out a sorted sequence, and shows that a BST is, in effect, a dynamic sorted list you can also splice into and search.

The catch: height is everything

Every operation above costs $O(h)$. So the BST is fast exactly when $h$ is small. The best case is a balanced tree, where the two subtrees of each node have nearly equal size; then $h=\Theta (\log n)$ and every operation is $\Theta (\log n)$.

The worst case is a disaster. Suppose we insert keys in sorted order: $1,2,3,\dots ,n$. Each new key is larger than everything present, so it walks all the way right and attaches as the rightmost leaf. The tree degenerates into a single descending path, a glorified linked list:

Now $h=n-1$, and search, insert, and successor all degrade to $\Theta (n)$, no better than scanning an unsorted array.⁴ The very flexibility that made insertion easy (new keys land as leaves wherever the path takes them) lets an unlucky or adversarial insertion order ruin the shape.

This is the central tension of binary search trees:

We cannot control the order in which keys arrive. So the fix is to make the tree rebalance itself as keys come and go, forcing $h=O(\log n)$ no matter what. Randomized BSTs (and treaps) achieve $\Theta (\log n)$ height in expectation; balanced search trees — red-black trees, AVL trees, B-trees — guarantee $O(\log n)$ height in the worst case by maintaining extra structural invariants and repairing them after each update. That repair machinery is the subject of the next lesson.

Takeaways

• A binary search tree stores keys under the BST property (left subtree $\le$ node $\le$ right subtree, recursively), so searching follows one root-to-leaf path.
• Search, insert, minimum, maximum, successor, predecessor all walk a single vertical path and cost $O(h)$; new keys enter as leaves.
• An inorder walk emits the keys in sorted order in $\Theta (n)$ time; the order is baked into the shape.
• Performance hinges entirely on height: $\Theta (\log n)$ when balanced, but $\Theta (n)$ for a degenerate (e.g. sorted-insertion) tree.
• Because we cannot control insertion order, we need trees that rebalance themselves to guarantee $h=O(\log n)$, the motivation for balanced search trees.