Binary Search Trees

Chapter 1: The BST Property

A binary search tree is a binary tree (each node has at most two children) where every node satisfies one rule:

Think of each node as a decision point. If you are looking for a value, the current node tells you which way to go: left if smaller, right if larger. This is exactly how binary search works on a sorted array — but now the "middle element" is a node, and the "halves" are subtrees.

Here is a concrete example. Consider the keys [2, 5, 7, 10, 12, 15, 20]. One valid BST is:

But this is NOT the only valid BST for those keys. The same set of keys can form many different tree shapes depending on insertion order. For example, inserting in sorted order [2, 5, 7, 10, 12, 15, 20] produces a completely different tree — a straight chain leaning right, like a linked list. We will see why this matters in Chapter 6.

The Node Structure

Each node in a BST stores four things:

python
class Node:
    def __init__(self, key):
        self.key = key       # the value stored at this node
        self.left = None    # pointer to left child (smaller keys)
        self.right = None   # pointer to right child (larger keys)
        self.parent = None  # pointer to parent (needed for successor)

The parent pointer is optional — some implementations omit it and use recursion or a stack to navigate upward. CLRS includes it because it simplifies the successor and delete algorithms.

Inorder Traversal Produces Sorted Output

Here is the most important consequence of the BST property: if you visit every node by going left-first, then the current node, then right (this is called inorder traversal), you visit the keys in sorted order.

This is not a coincidence. The BST property guarantees that everything to the left is smaller and everything to the right is larger. Inorder traversal respects this ordering at every level of recursion.

python
def inorder(node):
    """Visit all nodes in sorted order. O(n) time."""
    if node is None:
        return
    inorder(node.left)    # visit left subtree (all smaller keys)
    print(node.key)       # visit current node
    inorder(node.right)   # visit right subtree (all larger keys)

The simulation below lets you build your own BST. Type a number and press Insert. Click any node to verify the BST property — the left subtree highlights in one color (all smaller), the right subtree in another (all larger). Press "Inorder Walk" to see the sorted traversal animated.

Chapter 2: Search, Min, Max, Successor, Predecessor

Now that we have a BST, the first question is: how do we find a specific key? The answer falls straight out of the BST property.

Search

Start at the root. Compare the target key k with the current node's key. If k equals the node's key, you found it. If k is smaller, go left. If k is larger, go right. If you hit a null pointer (fell off the tree), the key is not present.

python
def search(node, k):
    """Search for key k in BST rooted at node. O(h) time."""
    if node is None or node.key == k:
        return node             # found it, or it doesn't exist
    if k < node.key:
        return search(node.left, k)   # k is smaller — go left
    else:
        return search(node.right, k)  # k is larger — go right

This traces a single path from root to some node (or to null). The number of comparisons equals the depth of the target node. The worst case is the tree's height h. So search is O(h).

python
def search_iter(node, k):
    while node is not None and node.key != k:
        if k < node.key:
            node = node.left
        else:
            node = node.right
    return node

Minimum and Maximum

The BST property tells us exactly where the smallest and largest keys live. The minimum is the leftmost node — keep going left until you cannot go further. The maximum is the rightmost node.

python
def minimum(node):
    """Go all the way left. O(h)."""
    while node.left is not None:
        node = node.left
    return node

def maximum(node):
    """Go all the way right. O(h)."""
    while node.right is not None:
        node = node.right
    return node

Successor and Predecessor

The successor of a node x is the node with the smallest key greater than x.key — the next node in sorted order. Finding it has two cases:

Case 1: If x has a right subtree, the successor is the minimum of that right subtree. Think about it: everything in the right subtree is larger than x, and the minimum of that subtree is the smallest among those larger values.

Case 2: If x has no right subtree, the successor is the lowest ancestor of x whose left child is also an ancestor of x (or x itself). In other words: go up until you turn right. The first time you go up from a left child, that parent is the successor.

python
def successor(x):
    """Find the node with the smallest key > x.key. O(h)."""
    if x.right is not None:
        return minimum(x.right)    # Case 1: min of right subtree
    # Case 2: go up until we turn right
    y = x.parent
    while y is not None and x == y.right:
        x = y
        y = y.parent
    return y  # None if x is the maximum

The predecessor is symmetric: if x has a left subtree, it is the maximum of the left subtree. Otherwise, go up until you turn left.

The simulation below lets you search for keys and find successors. Click "Search" to trace the search path. Click any node, then "Find Successor" to see the successor algorithm in action.

Chapter 3: Insertion

Inserting a new key into a BST is beautifully simple: do a search for the key, and when you fall off the tree (hit a null pointer), that is where the new node goes. The new node is always added as a leaf — it never displaces existing nodes.

The Algorithm

Walk down from the root, going left or right at each node just like search. Keep track of the trailing parent — the last non-null node you visited. When you reach null, create the new node and attach it as the left or right child of that trailing parent.

python
def insert(tree, z):
    """Insert node z into BST. z.key is already set. O(h)."""
    y = None           # trailing parent
    x = tree.root      # current node, starts at root

    # Phase 1: Walk down to find the insertion point
    while x is not None:
        y = x                      # remember the parent
        if z.key < x.key:
            x = x.left             # go left
        else:
            x = x.right            # go right

    # Phase 2: Attach the new node
    z.parent = y
    if y is None:
        tree.root = z              # tree was empty
    elif z.key < y.key:
        y.left = z                 # attach as left child
    else:
        y.right = z                # attach as right child

Worked Example

Let us insert 13 into this tree:

The key insight: insertion preserves the BST property automatically. By following the same path that search would take, we guarantee that the new node ends up in the correct position relative to every ancestor.

The simulation below shows insertion in real time. Type a key and watch it flow down the tree to its final position.

Time Complexity

Insertion traces a single root-to-leaf path, just like search. The work is O(h), where h is the height. For a balanced tree with n nodes, h = O(log n), so insertion is O(log n). For a degenerate chain, h = O(n), so insertion becomes O(n) — no better than a sorted array.

Chapter 4: Deletion

Deletion is the hardest BST operation. Inserting a node only adds a leaf, but deleting a node might remove an internal node with children — and those children need to be reconnected without breaking the BST property. There are three cases.

Case 1: Deleting a Leaf (No Children)

The simplest case. The node has no children, so just remove it. Update the parent's pointer (left or right) to null.

Case 2: Deleting a Node with One Child

The node has exactly one child. Bypass the node: connect the node's child directly to the node's parent. The child "moves up" to take the deleted node's place.

Why does this work? Node 2 was in the left subtree of 10, so it is ≤ 10. Node 5 was the left child of 10 and 2 was in 5's subtree, so 2 was already in 10's left subtree. The BST property is preserved.

Case 3: Deleting a Node with Two Children

This is the tricky case. The node has both a left and right child. You cannot just remove it — both subtrees need a parent. The solution: find the node's successor (the smallest node in the right subtree), swap it into the deleted node's position, then delete the successor from its original position.

Why the successor? Because it is the one node that can sit between the left subtree (all smaller) and the right subtree (all larger) without violating the BST property. And crucially: the successor has at most one child (it has no left child, because if it did, that left child would be smaller and the successor would not be the minimum of the right subtree).

CLRS defines a helper function transplant that replaces one subtree with another:

python
def transplant(tree, u, v):
    """Replace subtree rooted at u with subtree rooted at v."""
    if u.parent is None:
        tree.root = v              # u was the root
    elif u == u.parent.left:
        u.parent.left = v          # u was a left child
    else:
        u.parent.right = v         # u was a right child
    if v is not None:
        v.parent = u.parent        # update v's parent pointer

Now the full delete algorithm:

python
def delete(tree, z):
    """Delete node z from BST. O(h)."""
    if z.left is None:
        transplant(tree, z, z.right)       # Case 1 or 2a: no left child
    elif z.right is None:
        transplant(tree, z, z.left)        # Case 2b: no right child
    else:
        # Case 3: two children
        y = minimum(z.right)               # y = successor of z
        if y.parent != z:
            # y is deeper in the right subtree, not z's direct child
            transplant(tree, y, y.right)   # replace y with y's right child
            y.right = z.right              # y takes over z's right subtree
            y.right.parent = y
        transplant(tree, z, y)             # replace z with y
        y.left = z.left                    # y takes over z's left subtree
        y.left.parent = y

The simulation below lets you delete any node. Click a node to select it, then press "Delete." The algorithm identifies the case and shows the operation step by step.

Chapter 5: Tree Traversals

We saw inorder traversal in Chapter 1 — it visits nodes in sorted order. But there are three other important ways to walk through a tree, and each one has distinct applications.

The Four Traversal Orders

For the example tree [10, 5, 15, 2, 7, 12, 20]:

python
def preorder(node):
    if node is None: return
    print(node.key)          # visit BEFORE children
    preorder(node.left)
    preorder(node.right)

def postorder(node):
    if node is None: return
    postorder(node.left)
    postorder(node.right)
    print(node.key)          # visit AFTER children

from collections import deque
def level_order(root):
    if root is None: return
    q = deque([root])
    while q:
        node = q.popleft()
        print(node.key)      # visit level by level
        if node.left:  q.append(node.left)
        if node.right: q.append(node.right)

Morris Traversal: O(1) Space Inorder

The recursive approaches use O(h) stack space (either from the call stack or an explicit stack). Morris traversal achieves inorder traversal using O(1) extra space by temporarily threading the tree — making the rightmost node of each left subtree point back to the current node.

python
def morris_inorder(root):
    """Inorder traversal with O(1) extra space."""
    current = root
    while current is not None:
        if current.left is None:
            print(current.key)         # no left subtree — visit now
            current = current.right
        else:
            # Find inorder predecessor (rightmost in left subtree)
            pred = current.left
            while pred.right is not None and pred.right != current:
                pred = pred.right

            if pred.right is None:
                # Thread: make pred point back to current
                pred.right = current
                current = current.left
            else:
                # Thread already exists — we've visited left subtree
                pred.right = None      # unthread (restore tree)
                print(current.key)     # visit now
                current = current.right

The simulation below shows all four traversals on the same tree. Watch the visit order animate for each one.

Chapter 6: BST Performance

Everything in a BST — search, insert, delete, successor — runs in O(h) time, where h is the tree's height. So the fundamental question is: how tall is the tree?

Best Case: Balanced Tree

A complete binary tree with n nodes has height h = floor(log₂ n). Every level is fully packed except possibly the last. With n = 1,000,000 nodes, h = 19. That means search takes at most 19 comparisons. Extraordinary.

Worst Case: Degenerate Tree

If you insert keys in sorted order (1, 2, 3, 4, ..., n), each new key is larger than all existing keys, so it always goes to the rightmost position. The result is a straight chain — every node has only a right child. The height equals n - 1. Search becomes O(n), exactly like scanning a linked list. You have lost every advantage of the tree structure.

Average Case: Random Insertions

If you insert n keys in random order (each of the n! permutations equally likely), the expected height is O(log n). More precisely, the expected height is approximately 4.311 · ln(n) ≈ 2.99 · log₂(n). This was proven by Reed (2003) after decades of research.

The intuition: random insertion is unlikely to produce long chains. Most of the time, about half the remaining keys go left and half go right at each node, giving a roughly balanced split. It is not perfectly balanced, but close enough that the height grows logarithmically.

This is the showcase simulation. You can insert keys manually, or generate a batch of random, sorted, or reverse-sorted keys. Watch how the tree shape changes dramatically based on insertion order. The height metric updates in real time.

Chapter 7: BSTs in Practice

Plain BSTs are a theoretical foundation. Nobody ships them to production. Every real-world BST is a self-balancing variant that guarantees O(log n) height regardless of insertion order. Let us survey the major ones.

AVL Trees (Adelson-Velsky and Landis, 1962)

An AVL tree maintains a strict balance invariant: for every node, the heights of the left and right subtrees differ by at most 1. After every insertion or deletion, the tree checks the balance factor (height of left subtree minus height of right subtree) at each ancestor of the modified node. If the factor exceeds ±1, the tree performs rotations — local restructurings that restore balance.

Red-Black Trees (Bayer 1972, Guibas & Sedgewick 1978)

A Red-Black tree uses a looser balance invariant based on coloring nodes red or black. The five properties guarantee that no root-to-leaf path is more than twice as long as any other, which bounds the height to h ≤ 2 log₂(n+1).

B-Trees (Bayer & McCreight, 1972)

B-trees are the workhorse of databases and file systems. Unlike binary trees (2 children per node), B-trees have up to thousands of children per node. Each node stores multiple keys, so a single disk read fetches hundreds of keys at once. This minimizes disk I/O — the bottleneck in database operations.

When NOT to Use BSTs

BSTs are not always the right answer. Hash tables beat them for exact-match lookups.

Chapter 8: Interview Arsenal

Operation Cheat Sheet

The Five Core Interview Problems

1. Validate BST

Given a binary tree, determine if it is a valid BST. The naive approach — checking each node's children — is WRONG. You must check that each node's value is within the valid range defined by all its ancestors.

python
def is_valid_bst(node, lo=float('-inf'), hi=float('inf')):
    """Validate BST by passing valid range down. O(n) time, O(h) space."""
    if node is None:
        return True
    if node.key <= lo or node.key >= hi:
        return False
    return (is_valid_bst(node.left, lo, node.key) and
            is_valid_bst(node.right, node.key, hi))

2. Kth Smallest Element

Find the k-th smallest element in a BST. Inorder traversal visits nodes in sorted order, so the k-th node visited is the answer.

python
def kth_smallest(root, k):
    """O(h + k) time — traverse inorder, stop at k-th."""
    stack = []
    current = root
    count = 0
    while stack or current:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        count += 1
        if count == k:
            return current.key
        current = current.right
    return None

Follow-up: if you need to answer many kth-smallest queries and the tree is modified between queries, augment each node with a size field (count of nodes in its subtree). Then kth smallest is O(log n) by comparing k with the left subtree size.

3. Lowest Common Ancestor (LCA)

Given two nodes p and q in a BST, find their lowest common ancestor. The BST property makes this easy: if both p and q are smaller than the current node, the LCA is in the left subtree. If both are larger, it is in the right. Otherwise, the current node IS the LCA (or one of p, q is the current node).

python
def lca(root, p, q):
    """O(h) time — follow the BST property."""
    while root:
        if p.key < root.key and q.key < root.key:
            root = root.left       # both in left subtree
        elif p.key > root.key and q.key > root.key:
            root = root.right      # both in right subtree
        else:
            return root            # split point = LCA

4. Serialize and Deserialize BST

Serialize a BST to a string and reconstruct it. For a BST (not a general binary tree), preorder traversal alone is sufficient — the BST property lets you reconstruct the tree without null markers.

python
def serialize(root):
    """Preorder traversal. O(n)."""
    if not root: return []
    return [root.key] + serialize(root.left) + serialize(root.right)

def deserialize(preorder):
    """Reconstruct BST from preorder. O(n) with bounds."""
    def build(lo, hi):
        if not preorder or preorder[0] < lo or preorder[0] > hi:
            return None
        val = preorder.pop(0)
        node = Node(val)
        node.left = build(lo, val)
        node.right = build(val, hi)
        return node
    return build(float('-inf'), float('inf'))

5. Construct BST from Preorder

Given a preorder traversal of a BST, reconstruct the tree. This is the same as deserialize above. The first element is the root. All subsequent elements smaller than the root go to the left subtree; all larger go to the right subtree. Recurse.

Debug Scenario

"Our BST search returns the wrong result after deletion." Systematic diagnosis:

LeetCode Pattern Map

Chapter 9: Connections

Binary search trees are the foundation on which much of computer science is built. Every self-balancing tree, every database index, every ordered collection in every standard library traces back to the ideas in this chapter.

What We Covered

Where BSTs Lead

Related Lessons

CLRS Ch 11: Hash Tables — the alternative when you only need exact-match lookups. O(1) expected but no ordered operations.

CLRS Ch 7: Quicksort — quicksort's partition is the sorting analog of BST insertion. Inserting n random keys into a BST produces the same comparisons as quicksort on those keys.

CLRS Ch 15: Dynamic Programming — optimal BST construction (Section 15.5) uses DP to find the tree shape that minimizes expected search cost.

"An algorithm must be seen to be believed." — Donald Knuth