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 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.²

An unsuccessful search behaves the same way. Searching for $k=4$ in this tree compares $4<6$ (go left), $4>3$ (go right), $4<5$ (go left), and finds $5$'s left child is nil: the key is absent, and the search reports it after $h+1=3$ comparisons, never more. The nil that ends a failed search is not wasted information: it marks where the key would go, which is the observation insertion is built on.

$\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 marks 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 keeps insertion simple but also lets the tree's shape degrade, as shown below.

Tracing $\text{Tree-Insert}$ with $key(z)=4$ on our running tree: $x$ starts at the root $6$ with $y=\text{nil}$. Since $4<6$, the trailing pointer $y$ moves to $6$ and $x$ descends left to $3$. Since $4>3$, $y$ moves to $3$ and $x$ descends right to $5$. Since $4<5$, $y$ moves to $5$ and $x$ descends left, to nil. The loop exits with $y=5$; because $4<5$, the new node becomes $5$'s left child. Three comparisons, one pointer assignment, done.

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).

Trace both cases on the running tree. For $x=6$ (case 1): $right(6)=8$ is non-nil, so we return $\text{Tree-Minimum}$ of the subtree at $8$: descend left from $8$ to $7$, and $7$ has no left child, so the successor is $7$. Correct: $7$ is the smallest key exceeding $6$. For $x=5$ (case 2): $5$ has no right subtree, so we climb. First iteration: $y=3$ and $5=right(3)$, so $x\leftarrow 3$, $y\leftarrow 6$. Second test: $3=left(6)$, not a right child, so the loop stops and returns $6$, the first ancestor reached by moving up-and-right, which is precisely the smallest key greater than everything in $3$'s subtree. The climb can also run off the top: for $x=9$ the loop ascends $9\to 8\to 6$ (each a right child of its parent) and exits with $y=\text{nil}$; $9$ is the maximum and has no successor. A predecessor trace mirrors this: for $x=7$, which has no left subtree, we climb while $x$ is a left child ($7=left(8)$, so $x\leftarrow 8$), then stop because $8=right(6)$, returning $6$.

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 first two cases are pure pointer splices, and both are handled by the same two branches of $\text{Tree-Delete}$: when $left(z)$ is nil we transplant $right(z)$ into $z$'s place (this covers the leaf case too, transplanting nil), and symmetrically when $right(z)$ is nil. Concretely, in the tree below, deleting the leaf $2$ calls $\text{Transplant}(T,2,\text{nil})$: since $2=left(3)$, the assignment $left(3)\leftarrow \text{nil}$ detaches it and nothing else moves. Deleting $8$, which has only the child $9$, calls $\text{Transplant}(T,8,9)$: since $8=right(6)$, we set $right(6)\leftarrow 9$ and $parent(9)\leftarrow 6$, and $9$ rises one level with its subtree intact; every key in it is still $>6$, so the BST property holds.

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:

Follow the pointer surgery step by step. We delete $z=5$, the root. Both children exist, so the third branch runs: $y\leftarrow \text{Tree-Minimum}(8)=6$ (from $8$, one step left, then no further). Here $parent(y)=8\ne z$, so the inner fix-up fires first: $\text{Transplant}(T,6,7)$ lifts $6$'s right child $7$ into $6$'s old slot ($left(8)\leftarrow 7$), then $right(6)\leftarrow 8$ and $parent(8)\leftarrow 6$ hand $z$'s entire right subtree to $y$. Now $\text{Transplant}(T,5,6)$ makes $6$ the root, and $left(6)\leftarrow 3$, $parent(3)\leftarrow 6$ attach the untouched left subtree. The result is the tree on the right: $6$ sits where $5$ was, $7$ sits where $6$ was, and every ordering relation still holds because $6$ was the smallest key in the right subtree: everything remaining there is larger, and everything on the left was already smaller. When the successor is $z$'s direct child ($parent(y)=z$), the inner fix-up is skipped: $y$'s right subtree is already in the correct position relative to $y$, and the final transplant alone suffices. Why the successor and not some other key? Only $z$'s successor or predecessor can replace $z$ without reordering: the replacement must be larger than all of $z$'s left subtree and smaller than all of its right subtree except itself, and the successor (minimum of the right subtree) is one of exactly two keys with that property.

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. And sorted input is not a contrived adversary: it is one of the most common inputs in practice: keys read from a sorted file, timestamps arriving in order, sequential IDs from a database. Reverse-sorted input produces the mirror-image left path, and nearly-sorted input produces a tree that is nearly a path. Building a BST naively from data that happens to be ordered is a classic performance bug: the code is correct, the tests pass on small shuffled inputs, and production slows to a crawl.

How bad is a typical tree, as opposed to a worst-case one? There is a positive result here, with an important caveat about what typical means. Call a BST randomly built if it results from inserting $n$ distinct keys in uniformly random order into an empty tree.

So if insertion order were genuinely random, plain BSTs would be fine on average: the expected height is within a constant factor of the optimal ${\log }_{2}n$ (the constant in the known bounds is roughly $3$). The caveats: first, the theorem randomizes over insertion orders, not over tree shapes; it is a statement about a random process, and real inputs (sorted, nearly sorted, adversarial) need not look anything like a random permutation. Second, the guarantee is only in expectation and says nothing once deletions mix into the workload; the classical analysis covers insertion-only sequences. Randomized structures such as treaps enforce the random-order behavior regardless of the actual arrival order, which is one principled fix. The other is to enforce balance structurally.

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.

from collections.abc import Iterator
from typing import Generic, Optional, TypeVar

from comparable import Comparable

Key = TypeVar("Key", bound=Comparable)

class BSTNode(Generic[Key]):
  """
    One tree node: its key plus links to its left child, right child,\n
    and parent. A link is None where the corresponding node is absent;\n
    the root is the unique node whose parent is None.\n
  """

  def __init__(self, key: Key) -> None:
    self.key: Key = key
    self.left: Optional[BSTNode[Key]] = None
    self.right: Optional[BSTNode[Key]] = None
    self.parent: Optional[BSTNode[Key]] = None

  def __repr__(self) -> str:
    return f"BSTNode({self.key!r})"

class BinarySearchTree(Generic[Key]):
  """
    An ordered dictionary of keys kept under the BST property.\n
    Supports search, insert, delete, minimum, maximum, predecessor,\n
    successor, and an inorder walk that yields the keys in sorted order.\n
    Every update keeps the structural invariant; performance is O(height).\n
  """

  def __init__(self) -> None:
    self.root: Optional[BSTNode[Key]] = None
    self._size: int = 0

  def search(self, key: Key) -> Optional[BSTNode[Key]]:
    """
      The node carrying `key`, or None if no such node exists.\n
      Walk down from the root: stop on a match, go left when `key` is\n
      smaller, right when larger. One node per level, so O(h).\n
    """
    # branch left or right by comparison until the key or a dead end.
    current: Optional[BSTNode[Key]] = self.root
    while current is not None and key != current.key:
      if key < current.key:
        current = current.left
      else:
        current = current.right

    return current

  def __contains__(self, key: Key) -> bool:
    return self.search(key) is not None

  @staticmethod
  def minimum(node: BSTNode[Key]) -> BSTNode[Key]:
    """
      The node with the smallest key in the subtree rooted at `node`:\n
      follow `left` links until they run out.\n
    """
    current: BSTNode[Key] = node
    while current.left is not None:
      current = current.left
    return current

  @staticmethod
  def maximum(node: BSTNode[Key]) -> BSTNode[Key]:
    """
      The node with the largest key in the subtree rooted at `node`:\n
      follow `right` links until they run out.\n
    """
    current: BSTNode[Key] = node
    while current.right is not None:
      current = current.right
    return current

  def min_key(self) -> Optional[Key]:
    """
      The smallest key in the whole tree, or None if it is empty.\n
    """
    return None if self.root is None else self.minimum(self.root).key

  def max_key(self) -> Optional[Key]:
    """
      The largest key in the whole tree, or None if it is empty.\n
    """
    return None if self.root is None else self.maximum(self.root).key

  def insert(self, key: Key) -> BSTNode[Key]:
    """
      Insert `key` as a new leaf, preserving the BST property.\n
      Trace the search path with a trailing pointer to the parent;\n
      when the walk falls off the tree, hook the leaf in there. O(h).\n
    """
    node: BSTNode[Key] = BSTNode(key)
    parent: Optional[BSTNode[Key]] = None
    current: Optional[BSTNode[Key]] = self.root

    # descend to the empty slot where `key` belongs, trailing the parent.
    while current is not None:
      parent = current
      if key < current.key:
        current = current.left
      else:
        current = current.right

    # hook the new leaf onto the side of `parent` it belongs on.
    node.parent = parent
    if parent is None:  # tree was empty
      self.root = node
    elif key < parent.key:
      parent.left = node
    else:
      parent.right = node

    self._size += 1
    return node

  def successor(self, node: BSTNode[Key]) -> Optional[BSTNode[Key]]:
    """
      The node with the smallest key greater than `node`'s, or None if\n
      `node` holds the maximum. With a right subtree, it is that\n
      subtree's minimum; otherwise climb until moving up a left link.\n
    """
    if node.right is not None:
      return self.minimum(node.right)

    # climb while `node` is a right child; the first left turn is the answer.
    current: BSTNode[Key] = node
    ancestor: Optional[BSTNode[Key]] = node.parent
    while ancestor is not None and current is ancestor.right:
      current = ancestor
      ancestor = ancestor.parent
    return ancestor

  def predecessor(self, node: BSTNode[Key]) -> Optional[BSTNode[Key]]:
    """
      The mirror of `successor`: the node with the largest key smaller\n
      than `node`'s, or None if `node` holds the minimum.\n
    """
    if node.left is not None:
      return self.maximum(node.left)

    current: BSTNode[Key] = node
    ancestor: Optional[BSTNode[Key]] = node.parent
    while ancestor is not None and current is ancestor.left:
      current = ancestor
      ancestor = ancestor.parent
    return ancestor

  def _transplant(
    self,
    target: BSTNode[Key],
    replacement: Optional[BSTNode[Key]],
  ) -> None:
    """
      Put the subtree `replacement` where the subtree `target` was,\n
      rewiring `target`'s parent. Does not touch `replacement`'s own\n
      children; the caller fixes those up.\n
    """
    # point `target`'s parent (or the root link) at `replacement`.
    parent: Optional[BSTNode[Key]] = target.parent
    if parent is None:  # target was the root
      self.root = replacement
    elif target is parent.left:
      parent.left = replacement
    else:
      parent.right = replacement

    # and give `replacement` its new parent back-pointer.
    if replacement is not None:
      replacement.parent = parent

  def delete(self, key: Key) -> bool:
    """
      Remove the node carrying `key`. Returns False if it is absent.\n
      No child: detach. One child: splice it up. Two children: the\n
      successor (right subtree's minimum, which has no left child) takes\n
      the slot. O(h).\n
    """
    node: Optional[BSTNode[Key]] = self.search(key)
    if node is None:
      return False
    self._delete_node(node)
    self._size -= 1
    return True

  def _delete_node(self, node: BSTNode[Key]) -> None:
    """
      Excise `node` from the tree via at most one Transplant plus a\n
      constant amount of pointer surgery.\n
    """
    # fewer than two children: splice the lone subtree (or None) up.
    if node.left is None:  # 0 or 1 (right) child
      self._transplant(node, node.right)
      return
    if node.right is None:  # exactly one (left) child
      self._transplant(node, node.left)
      return

    # two children: the successor (right subtree's min) takes the slot.
    successor: BSTNode[Key] = self.minimum(node.right)

    # if it sits deeper, detach it first, lifting its right child up.
    if successor.parent is not node:
      self._transplant(successor, successor.right)
      successor.right = node.right
      successor.right.parent = successor

    # move the successor into `node`'s place, inheriting its left subtree.
    self._transplant(node, successor)
    successor.left = node.left
    successor.left.parent = successor

  def inorder(self) -> Iterator[Key]:
    """
      Yield every key in nondecreasing order — left subtree, node, then\n
      right subtree. Visits each node once, so Theta(n).\n
    """

    def walk(node: Optional[BSTNode[Key]]) -> Iterator[Key]:
      if node is not None:
        yield from walk(node.left)
        yield node.key
        yield from walk(node.right)

    yield from walk(self.root)

  def height(self) -> int:
    """
      The number of edges on the longest root-to-leaf path; -1 for an\n
      empty tree, 0 for a single node. Operations cost O(height).\n
    """

    def depth(node: Optional[BSTNode[Key]]) -> int:
      if node is None:
        return -1
      return 1 + max(depth(node.left), depth(node.right))

    return depth(self.root)

  def __iter__(self) -> Iterator[Key]:
    return self.inorder()

  def __len__(self) -> int:
    return self._size

from typing import Any, Protocol, TypeVar


class Comparable(Protocol):
  """
    Anything orderable with `<` (int, float, str, tuple, date, …).\n
  """

  # `other` is position-only so built-ins (int, str, …), whose dunder
  # operands are position-only, structurally satisfy the protocol.
  def __lt__(self, other: Any, /) -> bool: ...
  def __gt__(self, other: Any, /) -> bool: ...
  def __le__(self, other: Any, /) -> bool: ...
  def __ge__(self, other: Any, /) -> bool: ...

Augmenting the tree

A BST is not only a sorted set; once you hang extra information on each node, the same $O(h)$ walk answers much richer queries. The general method, from CLRS's chapter on augmenting data structures, is to store a small summary in each node that can be recomputed from a node and its two children in $O(1)$, so rotations still repair it cheaply.

Order-statistic trees. Store in each node the size of its subtree. Then two new queries run in $O(h)$: select$(i)$, find the $i$-th smallest key, and rank$(x)$, count how many keys are $\le x$. Select descends by comparing $i$ against the left subtree's size; rank accumulates left-subtree sizes along the search path. This augmentation is what the LeetCode problem Kth Smallest Element in a BST wants, and what a balanced order-statistic tree gives in $O(\log n)$, the LeetCode Count of Smaller Numbers After Self is the same augmentation applied online. As a concrete trace: in a tree holding $\{1,3,5,7,9\}$ with $5$ at the root (left subtree size $2$), $\text{select}(4)$ sees $i=4>2+1$, subtracts the $3$ keys at-or-left of the root, and recurses for the $1$st smallest in the right subtree $\{7,9\}$, landing on $7$.

Interval and other summaries. Store the maximum endpoint in each subtree and the tree answers "does any stored interval overlap $[a,b]$?" in $O(\log n)$, the interval tree, taken up in Spatial Data Structures. Store subtree sums and you get the ordered analogue of a Fenwick tree. The lesson is that a self-balancing BST is a substrate: rank/select, dynamic order statistics, and stabbing queries are all one augmentation away, which is why balanced BSTs, not hash tables, back the ordered-map type (std::map, Java TreeMap) in standard libraries.⁶

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.
• Delete has three cases — leaf, one child, two children — all built on the $\text{Transplant}$ splice; the two-child case moves the successor into the deleted node's place, which preserves ordering because the successor is the minimum of the right subtree.
• 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. A randomly built BST has expected height $O(\log n)$, but that assumes random insertion order and no deletions; real inputs offer no such promise.
• Because we cannot control insertion order, we need trees that rebalance themselves to guarantee $h=O(\log n)$, the motivation for balanced search trees.