🧩 Data Structures & Algorithms · Chapter 12

Trees and binary search trees

A binary search tree is binary search that you can insert into. Feed it sorted data, though, and it quietly turns into a linked list.

Study this lesson free in the app →

The basics

A tree is a set of nodes connected parent-to-child, with one root at the top and no loops. A binary tree gives each node at most two children, left and right. A binary search tree (BST) adds one rule: every key in a node's left subtree is smaller than the node, and every key in its right subtree is larger.

The problem it solves: a sorted array gives O(log n) search but O(n) insert (everything shifts). A linked list gives O(1) insert but O(n) search. A BST keeps data in order and lets you insert and delete by walking one path from the root — O(h), where h is the tree's height.

The mental model: a road with a signpost at every junction: "smaller → turn left, bigger → turn right". Each turn rules out an entire side of the map.

The catch: h is log₂ n only if the tree stays bushy. Insert 1, 2, 3, 4, 5 in order and every node hangs to the right: h = n − 1, and search is O(n).

Explained

Insert 1,000,000 random keys into a BST and finding any key takes about 20–50 steps.

Insert the same keys already sorted and the tree becomes a single right-leaning chain: finding the last key takes 1,000,000 steps.

Same data, same code. The only difference is the shape, and shape is everything with trees.

Signposts at every junction

You're looking for house number 60 in a town where the roads branch like a tree.

At the first junction the sign says 50. Your number is bigger, so you turn right — and never think about the left half of town again.

Next sign: 70. Smaller → turn left. Next sign: 60. You're home after three junctions.

The town planner's only rule: every house down the left road is smaller than the sign, every house down the right road is bigger. Now imagine a lazy planner who built houses 10, 20, 30, 40, 50 in that order, each to the right of the last: one long street, and house 50 is at the very end.

The vocabulary and the rule

            50          ← root (depth 0)
          /    \
        30      70      ← depth 1
       /  \    /  \
     20   40  60   80   ← leaves (depth 2)

• Height = edges on the longest root-to-leaf path = 2 here. 7 nodes, height ⌊log₂ 7⌋ = 2.
• The subtree rooted at 30 is {30, 20, 40}.
• BST rule: all of 30's subtree < 50 < all of 70's subtree. Checking only parent–child pairs is not enough.

Operations, all O(h):

• Search: compare, go left or right, stop at a match or an empty spot.
• Insert: search for the key; the empty spot where you fall off is where it goes.
• Min / max: keep going left / right.

Build a bushy tree, then search

Each new key walks down from the root, turning left when smaller and right when larger, and settles in the first empty spot. Inserting the middle value first gives a perfectly balanced tree: searching for 60 visits 50 → 70 → 60, three nodes.

Sorted inserts: the tree becomes a list

Every key is bigger than all before it, so each one goes right, right, right… Height is 4 for 5 nodes: n − 1. Searching for 50 visits every node — O(n), no better than a linked list. This is why production trees rebalance themselves.

Delete — the three cases

def min_node(node):
    while node.left:
        node = node.left
    return node

def delete(root, key):
    if root is None:
        return None
    if key < root.key:
        root.left = delete(root.left, key)
    elif key > root.key:
        root.right = delete(root.right, key)
    else:
        if root.left is None:           # leaf or only a right child
            return root.right
        if root.right is None:          # only a left child
            return root.left
        succ = min_node(root.right)     # two children:
        root.key = succ.key             # copy the next-larger key here
        root.right = delete(root.right, succ.key)  # remove it below
    return root

def inorder(node, out):
    if node:
        inorder(node.left, out)
        out.append(node.key)
        inorder(node.right, out)
    return out          # a BST gives sorted keys

Every branch walks one path down: O(h) time, O(h) stack.

Keeping the tree short

shape            height     search/insert/delete
───────────────────────────────────────────────
balanced         ~log₂ n    O(log n)   (1M keys → ~20)
random inserts   ~2–3·log n O(log n) expected
sorted inserts   n − 1      O(n)       (1M keys → 1M)

Self-balancing trees rotate nodes after inserts and deletes to guarantee O(log n): red-black trees (Java TreeMap, C++ std::map, Linux's scheduler) and AVL trees (stricter balance, faster lookups).

On disk, databases use B-trees: each node holds hundreds of keys, so a billion rows fit in a tree only 3–4 levels deep — 3–4 disk reads per lookup.

Python has no built-in BST; for ordered data people use bisect on a sorted list or the sortedcontainers library.

Gotchas

• Validating by checking only children — 10 → right 15 → left 6 passes a parent-child check but 6 sits in 10's right subtree. Pass down (low, high) bounds instead.
• Assuming O(log n) — only true if balanced. Say "O(h), which is log n when balanced and n in the worst case".
• Forgetting to re-link on insert/delete — insert(root.left, key) without root.left = … loses the new node.
• Duplicates — decide a policy (ignore, count, or always go right) and say it out loud.
• Recursion depth — a degenerate tree of 10,000 nodes overflows Python's stack in a recursive walk.
• Binary tree ≠ BST — a binary tree only limits children to two; the ordering rule is what makes it searchable.

Words to know

In two minutes

• A tree is nodes linked parent → child with one root and no cycles; a binary tree has at most two children per node.
• BST rule: everything in the left subtree < node < everything in the right subtree — for the whole subtree, not just the children.
• Search, insert and delete walk one root-to-leaf path: O(h) time.
• Balanced: h ≈ log₂ n, so O(log n). Inserting sorted data builds a chain: h = n − 1, so O(n).
• Delete has three cases: leaf (remove), one child (splice it up), two children (copy the in-order successor, then delete it).
• In-order traversal of a BST yields the keys in sorted order — O(n) to list them all.
• Space: O(n) for the nodes; recursive operations add O(h) stack. Real systems use self-balancing trees (red-black, AVL) or B-trees on disk.

Test yourself

There are 8 questions, 4 puzzles and 6 recall cards for this lesson in the app — the recall cards come back on later days, just before you would forget.