57The binary search tree — order that stays searchable

In Chapter 56 we built the binary tree: nodes on the heap, two children each, hierarchy and nothing more. Here we add one strict rule to that skeleton, and it turns into a search engine. The problem it solves is a trade-off. A sorted array can binary-search in O(log n), but insert one value in the middle and every element after it has to shift — an O(n) tax on every change. A hash table gives O(1) lookup, but it throws order away, so it can't tell you the smallest key or every key between 100 and 200. The binary search tree keeps both sides of that deal. It stays sorted and stays fast to change, because it holds order not in memory positions but in pointers. So one question runs through the whole chapter: what does it cost to keep a collection sorted while it is still changing under your hands? By the end you'll insert, search, and delete in a BST, see exactly why one careless insertion order can rot it into a slow linked list, and learn the fix that runs every database index on Earth.

01One rule, wired into every pointer

Let's start from what we already have. When we built the binary tree back in Chapter 56, each node lived on the heap, holding its data and up to two child pointers, left and right. That was hierarchy, and nothing more. A BST is that same skeleton plus one strict invariant — a rule that must hold at every node, with no exceptions: everything in my left subtree is less than me; everything in my right subtree is greater than me. Notice how far that reaches. It covers not just my two children, but my entire left subtree, all the way down, and my entire right subtree. That single promise is what turns a plain tree into a search structure.

Because the rule holds everywhere, a BST has a handy trait you first met in the binary-tree chapter. Walk it in-order — left subtree, then the node, then right subtree — and the keys come out sorted, for free, with no sorting step. We built one and walked it:

class Node:
    __slots__ = ("key", "left", "right")   # three references, nothing else
    def __init__(self, key):
        self.key  = key
        self.left = None                    # < me
        self.right = None                   # > me

root = None
for k in [4, 2, 6, 1, 3, 5, 7]:            # inserted in this order
    root = insert(root, k)

out = []
inorder(root, out)
print(out)          # [1, 2, 3, 4, 5, 6, 7]   ← sorted, though we never sorted

Line by line: each Node is just three references — the key, a left pointer, and a right pointer. We insert seven keys in a jumbled order. Then an in-order walk prints them 1 2 3 4 5 6 7. The sorted output falls straight out of the invariant, because "smaller stuff is always on the left" is exactly what in-order visits first. The order isn't stored anywhere. It's implied by where the pointers go.

Now the memory bill, run for real. A node with __slots__ is the leanest a Python BST node gets, and here's what we measured:

import sys
sys.getsizeof(Node(30))          # 56   ← 16 GC + 16 header + 3×8 pointers
# a plain class (no __slots__):
sys.getsizeof(dict_node)         # 48   object…
sys.getsizeof(dict_node.__dict__)# 296  …plus its instance dict = 344 total
# the same 1000 ints in a Python list:
sys.getsizeof(list(range(1000))) # 8056 → ~8 bytes per reference

Read the tax. Every BST node costs 56 bytes at best (344 if you skip __slots__). Of that, only 24 bytes — three 8-byte references — actually carries data. The rest is Python's per-object overhead: Vol 1's ~32-byte object header, here split into a 16-byte GC header and a 16-byte object head. A plain list stores those same references at 8 bytes each in one contiguous block. So a BST is roughly 7× heavier per element than a list. You pay that overhead to buy something a list can't give you: sorted order that survives insertion and deletion in O(log n). Whether that trade is worth it is the whole question of the chapter.

The invariant isn't decoration. It's a machine for cutting the problem in half at every step →

02Search: a binary search that walks pointers

Here is where the invariant pays off. To find a key, start at the root and compare. There are three outcomes. Equal — you found it, stop. Target is smaller — the invariant guarantees it can only be in the left subtree, so the entire right subtree is eliminated in one comparison. Target is larger — go right, and the whole left subtree is gone. Each comparison throws away one of the two subtrees. That is binary search — the halving technique from Volume 3 — except instead of indexing into a sorted array, you are following pointers down a tree:

def search(root, target):
    node = root
    while node is not None:          # until we fall off the tree
        if target == node.key:
            return node              # found — stop
        elif target < node.key:
            node = node.left         # smaller → whole right subtree gone
        else:
            node = node.right        # larger  → whole left subtree gone
    return None                      # ran out of tree → not present

Line by line: we hold a moving pointer node, starting at the root. Each loop is one comparison. If equal, we're done. If target < node.key we step left; otherwise right. When node becomes None, we've walked off the tip of a branch without a match, so the key isn't there. The number of loops is exactly the number of levels we descend: the path length from root to where the key is (or would be).

So search costs O(h), where h is the tree's height — the longest root-to-leaf path. Here is the crux. If the tree is balanced, each level roughly doubles the node count (1, 2, 4, 8, …), so n nodes fit in about log₂ n levels, and search is O(log n). We built a million-node tree and searched it:

# tree of 1,000,000 keys, inserted in random order:
#   height              = 50        (log2(1,000,000) ≈ 19.9)
#   search steps for 20 random keys: min 17, max 35, avg 26.1

A million keys, and a lookup touches on average 26 nodes — not a million. That is the log at work: each of those 26 comparisons halved what was left. (The height is 50 rather than the ideal 20 because a randomly-built BST is only roughly balanced. More on that, and on how to force it down to 20, shortly.)

Search reads the tree. Insert has to grow it — and it turns out inserting is just searching for the empty spot where the key belongs →

03Insert: search for where it isn't, then hang a node

Here's the trick that makes insert almost free: it reuses search entirely. To add a key, you search for it — comparing and stepping left or right — until you fall off the bottom of the tree at a None. That spot is exactly where the key belongs, because the path you walked is the same path a future search will walk to find it. So you allocate a new node and hang it there. One walk down, one link:

def insert(root, key):
    if root is None:                 # empty spot found → this is the place
        return Node(key)
    if key < root.key:
        root.left  = insert(root.left,  key)   # belongs somewhere on the left
    elif key > root.key:
        root.right = insert(root.right, key)   # …or somewhere on the right
    # key == root.key: already present, do nothing (a BST holds a set)
    return root

Line by line: when you hit a None, you've arrived — return a fresh node, and the caller links it in. Otherwise compare and recurse into the correct subtree, re-attaching the (possibly grown) subtree on the way back up. Equal keys are ignored here, so this BST behaves as a set. The cost is the length of the walk — O(h) again, the same descent as search, plus one node allocation. The important part: the existing nodes never move. Unlike a sorted array, inserting into the middle of the key range shifts nothing. You only rewire one None into a pointer.

Insert always plants the node at the end of its search path. Which raises a dangerous question: what if every key's search path leads to the same side — every single time? →

04The catastrophe: sorted input collapses the tree into a list

Everything above assumed the tree is bushy — short and wide. But nothing in insert guarantees that. The shape is decided entirely by the order keys arrive in. Feed a BST already-sorted data and watch what happens. Insert 1, and it's the root. Insert 2 — it's bigger, so go right. Insert 3 — bigger than 1, go right; bigger than 2, go right again. Every new key is the largest so far, so every insert goes right, right, right. The tree grows a single right-leaning limb with no left children at all. We ran it and measured the heights:

# insert 1,2,3,4,5,6,7 in that order → height = 7   (a chain of 7)
# insert 4,2,6,1,3,5,7 (jumbled)      → height = 3   (a bushy tree)

#        n   sorted-insert height   random-insert height   log2(n)
#       15                     15                      8      3.9
#     1000                   1000                     20     10.0
#    10000                  10000                     30     13.3
#    30000                  30000                     36     14.9

Read the columns. Sorted insertion gives height exactly n — every node has one child, in a straight line. It is no longer a tree; it is a linked list that happens to store its "next" pointer in the right field. And a linked list means search is O(n): to find the last key you walk all n nodes. The BST's whole reason for existing — O(log n) — is gone. The random column shows what balance would give you instead: 1000 keys in height 20, 30000 keys in height 36, hugging log₂ n. Same keys, same code, same invariant — a 50× difference in height, decided only by arrival order.

We even timed the collapse by searching for the deepest key in each tree:

#   n     degenerate (chain)   balanced (random)
#  1000        115 µs               1.06 µs
#  2000        231 µs               1.06 µs
#  4000        462 µs               0.55 µs

The degenerate column doubles as n doubles — the fingerprint of O(n) — while the balanced column just sits near a microsecond whatever the size, the fingerprint of O(log n). At n=4000 the balanced tree answers roughly 800× faster for the same keys. (The timings are from this machine and will vary from run to run. The shapes — one line climbing, one flat — are what stays true.)

A structure whose whole value can be destroyed by sorted input is a structure begging for a guardian. Humans built one →

05The fix humans invented: trees that rebalance themselves

The degeneracy problem has a clean statement: after enough one-sided inserts, the tree gets tall. So the fix is a structure that notices when it's leaning and straightens itself back out — a self-balancing tree. The key mechanical trick is the rotation: a small, local rewiring of three or four pointers that lifts a deep subtree up and pushes a shallow one down, without breaking the left<node<right invariant. A rotation is O(1), because it touches only a constant number of pointers. It changes the tree's shape but not its sorted meaning.

Two famous designs wrap rotations in a self-balancing policy. You use their descendants constantly, so let's meet them by name. An AVL tree keeps every node's two subtree heights within 1 of each other; the moment an insert breaks that, it rotates. It's the strictest, so it's the shortest and the fastest to search. A red-black tree is looser. It colours nodes red or black and enforces rules that keep the longest path at most twice the shortest, which means fewer rotations on insert and delete — a better all-round trade. (We stay at the concept here. The promise is "height stays O(log n)"; the exact rotation cases are a topic of their own.) Red-black trees are not academic trivia. They are the ordered map and ordered set in your standard library: C++'s std::map/std::set, Java's TreeMap/TreeSet, and the Linux kernel's process scheduler and virtual-memory areas. Every time you iterate a Java TreeMap in sorted order, you are walking a balanced BST in-order.

Why fat nodes for disk? This is mandate #3 — how the machine gets the benefit — and it's the same cache story from Volume 3, one level down. Reading from a disk (even an SSD) happens in fixed blocks, typically 4 KB or more. And a single disk seek is painfully slow next to RAM: hundreds of thousands of times slower. A binary tree of a billion keys is about 30 levels deep, so a lookup could be 30 separate disk seeks — a disaster. A B-tree sizes each node to fill exactly one disk block, packing perhaps 100–500 keys into it. Now the tree is only 3–4 levels deep for a billion keys, because each level branches 100+ ways instead of 2. A lookup is 3–4 block reads instead of 30 seeks. The design move: match the node to the transfer unit of the storage. Pointer-chasing a skinny binary tree wastes almost the whole block it drags in; a B-tree makes every expensive block read carry hundreds of useful keys.

Search, insert, and balance handle growing the tree. One operation is still missing, and it's the only one with a genuine puzzle in it: taking a node out →

06Delete: the operation with a twist

Deleting from a BST has to preserve the invariant, and that makes it the one operation with real cases. First find the node (an O(h) search), then handle three situations, one for each number of children it has:

• No children (a leaf). Easiest: just null out the parent's pointer to it. The node vanishes; refcount drops to zero; Python reclaims it (Vol 1).
• One child. Splice it out — connect the node's parent directly to the node's single child. The subtree slides up one level, order intact.
• Two children. The puzzle. You can't just remove it — two subtrees would be orphaned. The classic fix: don't remove the node, overwrite its key with its in-order successor — the smallest key in its right subtree, which is exactly the next value in sorted order — then delete that successor (which, being leftmost, has at most one child, reducing to an easy case).

Why the successor works: the smallest key on the right is larger than everything on the left and smaller than everything else on the right. So it's the one value that can sit in the vacated spot without breaking left<node<right. We ran all three cases and checked that the in-order output stayed sorted after each:

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:                                     # found the node to remove
        if root.left  is None: return root.right   # 0/1 child
        if root.right is None: return root.left    # 1 child
        succ = root.right                          # 2 children:
        while succ.left is not None:               #   find in-order successor
            succ = succ.left                       #   (leftmost of right subtree)
        root.key = succ.key                        # overwrite, don't unlink
        root.right = delete(root.right, succ.key)  # delete the successor
    return root

Line by line: the first two branches are just search, recursing left or right and re-linking. Once the node is found: if a child is missing, return the other child (that covers the leaf and one-child cases in two lines). With two children, walk right and then left to the end to reach the successor, copy its key up into the current node, and delete the successor from the right subtree. The output confirmed that order held through every case:

# start:            [1, 2, 3, 4, 5, 6, 7, 8, 9]
# delete leaf 1:    [2, 3, 4, 5, 6, 7, 8, 9]
# delete 7 (1 child)[2, 3, 4, 5, 6, 8, 9]
# delete 3 (2 kids) [2, 4, 5, 6, 8, 9]   ← 3 replaced by successor 4
# delete root 5     [2, 4, 6, 8, 9]      ← new root is successor 6

Every line is still perfectly sorted — the invariant survived deletion of a leaf, a one-child node, a two-child node, and even the root. All of it is O(h): a search to find the node, plus a walk to the successor, both bounded by the height. In a balanced tree that's O(log n); in that degenerate chain it's O(n). The same tax hangs over delete as over everything else.

That question is the whole point of learning structures. The answer is the last idea in the chapter →

07When to reach for a tree — the access pattern is the answer

A hash table wins on a single point lookup — "is key X here, and what's its value?" — hands down, O(1) versus O(log n). If that is all you do, use the dict; don't reach for a tree just to feel clever. The tree earns its keep the moment your questions become ordered ones — the very questions a hash table, which scatters keys to random slots, physically cannot answer without scanning everything:

• Range queries. "All keys between 100 and 200." In a balanced BST: find 100 in O(log n), then walk in-order until you pass 200. A hash table would have to examine every key.
• Order statistics & neighbours. Smallest key, largest key, the next key above X, the previous key below X — all O(log n) in a tree, all impossible-without-a-scan in a hash.
• Sorted iteration. "Give me everything in order." An in-order walk, O(n) with no separate sort. A hash table would need to extract and sort, O(n log n).

That's the transferable move, mandate #5: choosing the structure is choosing which questions are cheap. Point lookup only → hash. Ordered questions on changing data → balanced tree. Ordered questions on data that rarely changes → don't even use a tree; sort an array once and binary-search it (Volume 3), because a contiguous array streams through cache far faster than a tree of scattered nodes. Here's the decision table:

A BST spends O(log n) to keep total order — every key rank exact. But a huge class of problems doesn't need the whole order — only "what's the most extreme one right now?" Give up full sorting, keep just that, and you get a structure so lean it lives in a flat array with no pointers at all. That's the heap, chapter 58 →