Data Structures
Lessons · #6 of 11

Binary Search Trees

Order in, log-time out

Binary search tree · path-walking search

size0
height0
compares0
init

Try it: Insert keys; search highlights the comparison path. Then hit break it: inserting sorted values collapses the tree into a linked list — height jumps from log n to n.

Why it matters

BSTs combine the fast lookup of arrays with the flexible insertion of linked lists. They're the foundation for sets, maps, and databases. Understanding BSTs is key to understanding balanced trees and efficient searching.

The idea

Remember the number guessing game? "Is it higher or lower?" Each answer eliminates half the possibilities.

A BST is that game in tree form. Every node follows one rule: left children are smaller, right children are larger.

To find a value:

  1. Start at root
  2. If value < node, go left. If value > node, go right.
  3. Repeat until found or reach null.

Each step eliminates half the tree - that's O(log n)... if the tree is balanced. If you insert sorted data, you get a linked list and O(n). That's why balanced trees exist.

Key takeaways

The BST invariant

Every operation on a BST must preserve one rule. State it once, you can prove correctness of every algorithm by checking the rule holds before and after:

BST invariant
For every node n: every key in n.left's subtree is strictly less than n.key, and every key in n.right's subtree is strictly greater.
Corollary — in-order traversal yields sorted order
Visit left recursively, then self, then right recursively. The recursive call on left returns keys all less than self.key; the call on right returns keys all greater. So the concatenation is sorted.
What "preserve" means in practice
Every insert/delete must end with the invariant still true everywhere. Insert is easy — you only add at a leaf, so the rule already holds. Delete is the hard case; see below.

Going deeper

Deletion — the three cases, walked through

This is the operation that makes engineers reach for AVL or Red-Black trees. Removing a node while preserving the invariant takes care.

Case 1 — leaf. Just detach it from its parent. The invariant is trivially preserved because no other node depended on this one.

    5                5
   / \              / \
  3   8     →      3
     /
    6           (delete 6 from right of 3)

Wait, that example removes 6 from the left of 8 — point is, leaves are free.

Case 2 — one child. Splice the child up into the deleted node's slot. The deleted node's parent now points at the child; the child's subtree was already invariant-compliant, so it stays compliant in the new position.

      5                5
     / \              / \
    3   8     →      3   6
        /
       6           (delete 8: it had only a left child, 6)

Case 3 — two children. You can't just promote either child — both have their own subtrees you'd have to merge somehow. The trick: find the in-order successor — the smallest key in the right subtree (equivalently, the leftmost leaf of right). Copy its value into the deleted node, then delete that successor from the right subtree (recursive call, but the successor itself has at most one child, so the recursion bottoms out at case 1 or 2).

      5                6
     / \              / \
    3   8     →      3   8
       / \              / \
      6   9            7   9
       \
        7              (delete 5: successor is 6;
                       copy 6 up, then delete the
                       original 6 — case 2 with right
                       child 7)

Why successor and not predecessor? Either works — the predecessor is the largest key in the left subtree. Most implementations alternate or pick one and stay consistent. The invariant is preserved because the successor was strictly greater than everything in the left subtree (so it's still greater after promotion) and strictly less than everything else in the right subtree (so the right subtree is still valid).

Why this all collapses without balance

The demo's break it button inserts already-sorted values. Every new node goes to the rightmost position — the tree becomes a linked list, height climbs to n, and search degrades to O(n). This is the motivation for the balanced trees lesson: the algorithms there rebalance after every insert and delete, so the height stays O(log n) no matter what order the inputs arrive.

Math details

Time Complexity (height h)
Search: O(h)
Insert: O(h)
Delete: O(h)
Min/Max: O(h)
Height bounds
Balanced: h = O(log n)
Unbalanced: h = O(n)

Implementation

fn search(node: Option<&Box<BstNode>>, key: i32)
    -> bool
{
    match node {
        None => false,
        Some(n) => {
            if key < n.data {
                search(n.left.as_ref(), key)
            } else if key > n.data {
                search(n.right.as_ref(), key)
            } else {
                true  // Found!
            }
        }
    }
}

Deletion Cases

Practice

Three problems built on the BST invariant:

→ Browse all practice problems