Chapter 6 — Trees: When Hierarchy Is the Shape

“I have seen all the works that are done under the sun, and behold, all is vanity and a striving after wind.” — but a tree, rightly built, is the rare thing that is not: “He is like a tree planted by streams of water that yields its fruit in its season, and its leaf does not wither. In all that he does, he prospers.” — Psalm 1:3

“The structure of a system tends to follow the structure of the data it operates on.” — folklore, after Fred Brooks

Why This Matters

Last week you built a hash table, and it was magic. Put a key in, get a value out, average O(1), no matter how big the table gets. You broke it with a flood of colliding keys, you watched the magic curdle into O(n), and then you fixed the hash and watched the magic come back. By the end you could say the one sentence that separates an architect from a memorizer: a hash table is average O(1), worst-case O(n), and gives you no order at all.

That last clause — no order at all — is the door into this week.

A hash table scatters your keys across its buckets by design. Two keys that are “next to each other” in any human sense — 17 and 18, “Aaron” and “Abel,” timestamps one second apart — land in completely unrelated buckets. The hash function’s whole job is to destroy the relationship between keys so they spread out evenly. Which means: ask a hash table “what’s the smallest key you hold?” or “give me every key between 100 and 200” or “iterate everything in sorted order,” and it cannot help you. It would have to look at every single bucket — O(n) — because it threw the order away the moment you put the data in.

Most of the time you don’t care. Membership is all you need, and the hash table is the right tool. But some of the time the order is the point. A leaderboard. An autocomplete that needs every word starting with “arch.” A calendar that needs the next event after 3:00 PM. A database that needs every row where price is between $10 and $20. For those, you need a structure that keeps its keys sorted and still answers fast.

This week’s answer is the binary search tree. And the shape it has — a root, branching into children, branching into children — is not an arbitrary trick. It is the natural shape of two things you already know intimately. First, hierarchy itself: a file system, an org chart, the DOM in a web page you’ll build in Phase 2, a genealogy. When the data is a hierarchy, the tree isn’t a clever encoding of it — the tree is it. Second, recursion, which you spent Chapter 7 of Coding 2 learning to think in. A tree is the data structure that recursion was born to walk: a tree is a node plus a left tree plus a right tree, and that sentence — a thing defined in terms of smaller copies of itself — is the definition of recursion wearing a different hat. If recursion ever felt like a parlor trick, trees are where it becomes the obvious, only-sane way to write the code.

The Christian question for the week is what grows from a root? The psalmist’s tree is planted by streams of water, rooted, fruitful in season. The vine of John 15 holds branches that bear fruit only while they abide in it — “I am the vine; you are the branches. Whoever abides in me and I in him, he it is that bears much fruit, for apart from me you can do nothing.” The image is not decoration. A tree is a structure where everything depends, through an unbroken chain of connection, on the root. Cut the root and the whole structure is orphaned memory. Sever a branch and everything below it is lost. We will lean on that picture when we delete a node and have to ask, carefully, what abides, and what is cut off?

6.1 — Recursion, Revisited: The Shape That Walks Itself

Before the vocabulary, the mindset. In Coding 2 you learned recursion: a function that calls itself on a smaller version of the problem, with a base case that stops the descent. You practiced it on factorials and on walking a directory of catechism files. It worked, but it may have felt a little forced — most of those problems had perfectly good loops.

Trees are where recursion stops feeling forced and starts feeling inevitable. Here is why. Look at the definition of a tree:

A binary tree is either empty, or a node holding a value plus a left binary tree and a right binary tree.

Read that again. The definition of a tree contains the word tree. A tree is a node plus two smaller trees. That is a recursive definition — a thing defined in terms of smaller copies of itself, with “empty” as the base case. And a recursive definition almost always wants recursive code. When you write a function to walk a tree, the shape of the function mirrors the shape of the data exactly:

def do_something(node):
    if node is None:        # base case: empty tree, nothing to do
        return
    do_something(node.left)     # recurse on the smaller left tree
    # ... work with node.value ...
    do_something(node.right)    # recurse on the smaller right tree

The function has the same shape as the data: base case for empty, then handle left, me, right. You are not forcing recursion onto the problem. The problem is recursive and the code is just admitting it. Every traversal in §6.5, the insert in §6.4, two of the three delete cases — all of them are three or four lines, because the recursion is doing the bookkeeping that a loop would force you to do by hand with an explicit stack.

Coach’s Note — If recursion still makes you nervous, trees are the cure, not the poison. On a list, recursion competes with a loop and usually loses on clarity. On a tree, recursion is the clear version and the loop is the painful one (you’d have to manage your own stack — which, foreshadowing, is exactly what level-order traversal does with a queue in §6.5). Watch how short the tree code is this chapter. That shortness is recursion finally being used for the job it was made for.

There is one cost to recursion you must keep in your peripheral vision, and it ties straight back to Coding 1. Every recursive call pushes a stack frame — the call stack is a real, finite region of memory. Walk a tree of height h and you go h frames deep. For a balanced tree, h ≈ log n, so a million nodes is ~20 frames deep — nothing. But for a degenerate tree (§6.7), h can be n, and a recursion n deep on a million nodes will blow Python’s recursion limit and crash. Hold that thought; it is the dark side of §6.7 and a reason the iterative versions in the code/ folder exist.

6.2 — The Vocabulary of Trees

Trees come with a small, precise vocabulary, borrowed half from botany and half from family trees (and, charmingly, drawn upside down — the root is at the top). You must own these words cold, because the rest of the chapter, the exercises, and the project all use them as if you do.

Here is a tree, with every term labeled:

                 (50)          <- ROOT: the single top node, no parent
                /    \
            (30)      (70)     <- 30 and 70 are CHILDREN of 50; 50 is their PARENT
            /  \      /  \
        (20)  (40)(60)  (80)   <- this whole bottom row are LEAVES (no children)

Two of these — depth and height — get confused constantly, so fix the difference now. Depth measures how far down you are from the root (count upward to the top). Height measures how far down the deepest leaf is below you (count downward to the bottom). The root’s depth is 0; the root’s height is the height of the whole tree. They are measured from opposite ends.

The one term that quietly does the most work is subtree. “The left subtree of node 50” means node 30 and everything under it — 30, 20, 40 — treated as a complete tree in its own right. Every recursive function in this chapter works by saying “handle this node, then recurse into the left subtree, then recurse into the right subtree,” and it can do that precisely because a subtree is a smaller tree with all the same rules. The subtree is the smaller copy of itself from §6.1.

Coach’s Note — Draw your trees. On paper, on a whiteboard, in the margin. The single highest-leverage habit in this entire chapter is drawing the tree before and after an operation. Every delete bug you will ever have is a bug you would have seen if you’d drawn the three nodes involved. The architect who can’t sketch the structure can’t reason about it. Pen in hand, always — exactly the discipline Coding 2 Chapter 1 demanded for reading code.

6.3 — From Binary Tree to Binary Search Tree

A binary tree is just the shape: every node has at most two children, a left and a right. That alone buys you nothing for searching — the values could be in any arrangement, and finding one would mean checking every node, O(n), same as an unsorted array.

The power comes from adding one rule. A binary search tree (BST) is a binary tree with an ordering invariant:

For every node in the tree: every key in its left subtree is less than the node’s key, and every key in its right subtree is greater than the node’s key.

That is the whole idea. Smaller to the left, larger to the right, recursively, at every node. Look back at the tree in §6.2 and check it: under 50, everything on the left (30, 20, 40) is less than 50, everything on the right (70, 60, 80) is greater. And it holds again at 30: 20 is to its left (smaller), 40 to its right (larger). The invariant is true at every node, all the way down. That is what makes it a search tree and not just a tree.

Why does that one rule buy you fast search? Because it lets you discard half the tree at every step, exactly like binary search on a sorted array (Coding 1). Want to know if 40 is in the tree? Start at the root, 50. Is 40 < 50? Yes — so if 40 is anywhere, it’s in the left subtree, and you can ignore the entire right subtree forever. Move to 30. Is 40 < 30? No, 40 > 30 — go right, ignore 30’s left. Move to 40. Found it. Three comparisons to search a seven-node tree, and on a balanced tree of a million nodes it would be about twenty comparisons. Each step throws away half of what’s left. That halving is log n, and it is the same halving that made binary search fast — but now it works on a structure you can also cheaply insert into, which a sorted array could not (insertion into a sorted array is O(n) because everything shifts; §2.6).

Here is the node and the skeleton, in Python:

class _Node:
    __slots__ = ("key", "left", "right")   # __slots__: save memory per node

    def __init__(self, key):
        self.key = key
        self.left = None       # a None child means "empty subtree here"
        self.right = None


class BST:
    def __init__(self):
        self._root = None      # an empty tree is just a root of None
        self._size = 0

Notice what a tree is at the memory level, and connect it to Chapter 3: like the linked list, a tree is pointers all the way down. There is no contiguous block, no array, no address arithmetic. Each node is a separately-allocated object somewhere on the heap, holding two references (left, right) to other scattered objects. That has the same consequence it had for linked lists: traversing a tree is cache-hostile (§2.2) — every step chases a pointer to a random heap location and loses the cache-line bet. A BST’s O(log n) is real, but its constant factor is worse than an array’s because of this pointer-chasing. File that away for §6.8; it is part of why a database doesn’t store its index as the naive BST you’re about to build.

Coach’s Note — The ordering invariant is a contract, in exactly the Coding 2 Chapter 2 sense. Every method you write — insert, delete, the lot — must preserve it: the tree must still satisfy “smaller left, larger right at every node” when your method returns. When a BST is buggy, it is almost always because some operation violated the invariant and left the tree in a state where search silently walks past the key it’s looking for. The way you debug a BST is the way you debug any contract: state the invariant, then check it held after every step.

6.4 — BST Operations: Insert, Search, Delete

Three operations define the BST. Two are easy and one — delete — is the genuinely tricky one that separates people who understand trees from people who copied a tree off the internet.

Search / contains

Search is the invariant turned into a walk. At each node: equal? found. Smaller? go left. Larger? go right. Fall off the bottom (None)? not here. It can be written recursively, but the iterative version is cleaner and uses no stack, so prefer it:

def contains(self, key):
    node = self._root
    while node is not None:
        if key == node.key:
            return True
        node = node.left if key < node.key else node.right
    return False

Cost: O(height). Each step goes down one level. On a balanced tree that’s O(log n); on a degenerate one it’s O(n) (§6.7). Hold the “height, not log n” precision — it is the entire point of §6.6 and §6.7.

Insert

Insert is search with a twist: walk down as if searching, and when you fall off the bottom (None), that empty spot is exactly where the new key belongs — because the ordering invariant left only one place it could go. Recursive insert reads beautifully because of the §6.1 shape:

def insert(self, key):
    self._root, inserted = self._insert(self._root, key)
    if inserted:
        self._size += 1

def _insert(self, node, key):
    if node is None:                      # base case: empty spot -> the key lives here
        return _Node(key), True
    if key < node.key:
        node.left, inserted = self._insert(node.left, key)
    elif key > node.key:
        node.right, inserted = self._insert(node.right, key)
    else:
        inserted = False                  # duplicate -> ignore (set semantics)
    return node, inserted

The pattern — “recurse into a subtree, then reassign the link to whatever the recursion returns” (node.left = self._insert(node.left, key)) — is the single most important pattern in tree code. The recursion returns the (possibly new) subtree, and you wire it back into the parent. Insert into an empty subtree returns a brand-new node; insert into a non-empty one returns the same node with its child updated. Either way the parent’s link is correct. Master this reassign-the-link pattern and delete will be tractable. Skip it and delete will be a nightmare of dangling references — the same orphaned-pointer bugs Coding 1 warned you about.

Cost: O(height), same as search — you walk down one path and add a leaf.

Delete — the three cases

Deletion is the hard one because removing a node can’t just blank it out: its children would be orphaned (cut from the root, exactly the John 15 image — a branch severed from the vine), and the ordering invariant must still hold afterward. There are three cases, and a correct delete handles all three. After you find the node to delete:

Case 1 — the node is a leaf (no children). Easiest. Just remove it; nobody hangs below it. The parent’s link to it becomes None.

delete 20 (a leaf):
        30                30
       /        ->         \
    (20)  40                40

Case 2 — the node has exactly one child. Splice the child up into the deleted node’s place. The single child (and its whole subtree) slides up; the invariant still holds because that subtree was already correctly ordered relative to everyone above.

delete 30 (one child, 40):
        50                50
       /        ->        /
    (30)                40
        \
         40

Case 3 — the node has two children. The hard case, and the one with the elegant trick. You cannot just promote one child — where would the other go? Instead, don’t remove the node at all — replace its key. Replace the deleted node’s key with its in-order successor: the smallest key in its right subtree. That key is, by the ordering invariant, larger than everything in the left subtree and smaller than everything else in the right subtree — exactly the property the deleted node’s key had, so the invariant is preserved. Then delete the successor from the right subtree. And here is why it terminates cleanly: the in-order successor is the leftmost node of the right subtree, so it has no left child, which means deleting it is always the easy Case 1 or Case 2. The hard case reduces to an easy case.

delete 50 (two children). Successor = smallest in right subtree = 60.
Copy 60 up into 50's spot, then delete the old 60 (a leaf -> Case 1):

        50                  60
       /  \      ->        /  \
     30    70            30    70
          /                   /
        (60)               (was 60, now gone)

Here is the whole delete, recursive, all three cases:

def delete(self, key):
    self._root, deleted = self._delete(self._root, key)
    if deleted:
        self._size -= 1

def _delete(self, node, key):
    if node is None:
        return None, False                    # key not found; tree unchanged
    if key < node.key:
        node.left, deleted = self._delete(node.left, key)
        return node, deleted
    if key > node.key:
        node.right, deleted = self._delete(node.right, key)
        return node, deleted

    # found it. THREE cases:
    if node.left is None:                      # Case 1 (leaf: right is None too) / Case 2
        return node.right, True
    if node.right is None:                     # Case 2 (only a left child)
        return node.left, True

    # Case 3: two children. Copy in-order successor's key, delete successor.
    successor_key = self._min_key(node.right)
    node.key = successor_key
    node.right, _ = self._delete(node.right, successor_key)
    return node, True

@staticmethod
def _min_key(node):
    while node.left is not None:               # leftmost node = smallest key
        node = node.left
    return node.key

Notice how Cases 1 and 2 collapse into two lines: if node.left is None, return node.right — which is None for a leaf (Case 1) and the lone child otherwise (Case 2). One check handles both. That collapse is not a trick; it’s the reassign-the-link pattern paying off. The full runnable version with a driver that exercises all three cases is code/bst_demo.py. Run it and watch the in-order output stay sorted through every deletion — that sorted-ness surviving is the proof the invariant held.

Cost of delete: O(height) — find the node (down one path), and in Case 3 find the successor (down one more path). Still bounded by the height.

Coach’s Note — Case 3 is the most-failed interview question in data structures, and it fails for one reason: people try to move nodes around (rewire pointers, promote a child, hang the other child somewhere). Don’t move nodes. Copy a key. The deleted node stays put; only its key changes, and then you delete the now-duplicated successor from below — where it is guaranteed to be an easy case. “Copy the successor’s key down, then delete the successor” is the whole sentence. Memorize the sentence, not the pointer gymnastics.

6.5 — Traversals: Four Ways to Walk a Tree

A traversal visits every node exactly once. There are four standard orders, and they are not interchangeable — each one is the right tool for a different job. Three are depth-first (go deep before going wide, using recursion / the call stack); one is breadth-first (go wide before going deep, using a queue). The runnable side-by-side is code/traversals.py.

For the tree below, here is what each traversal produces:

            (4)
           /   \
        (2)     (6)
        / \     / \
     (1) (3) (5) (7)

In-order is the whole point

Look at the in-order column: 1 2 3 4 5 6 7. Sorted. That is not a coincidence and it is the single most important fact in this chapter. In-order traversal of a BST yields its keys in ascending sorted order, every time. Why? Because “left, me, right” means: visit everything smaller than me (recursively, in order), then me, then everything larger than me (recursively, in order). The ordering invariant guarantees that’s exactly ascending order. The three depth-first traversals are three lines each:

def in_order(node, out):          # left, me, right -> SORTED
    if node is None:
        return
    in_order(node.left, out)
    out.append(node.key)
    in_order(node.right, out)

Swap the order of the three statements and you get pre-order (me first) or post-order (me last). Same skeleton, the §6.1 recursion shape, one line moved. This is why the BST is the answer to “I need fast lookup AND sorted iteration”: the hash table can do the lookup but never the sorted iteration; the BST does both, the second one for free as a side effect of its shape.

Level-order: the breadth-first one (callback to Chapter 4)

The fourth traversal is different in kind. Level-order visits the tree row by row: first the root, then both its children, then all four grandchildren, left to right. You cannot do this with the recursive call stack, because recursion is inherently depth-first — it dives all the way down one branch before backing up. To go across a level before going down, you need a queue — the first-in-first-out structure you built in Chapter 4.

The algorithm is short and worth memorizing, because it is breadth-first search (BFS) and you will use the exact same engine on graphs next week:

from collections import deque

def level_order(root):
    out = []
    if root is None:
        return out
    q = deque([root])                 # start with the root in the queue
    while q:
        node = q.popleft()            # take from the FRONT (FIFO)
        out.append(node.key)          # visit it
        if node.left is not None:
            q.append(node.left)       # enqueue children at the BACK
        if node.right is not None:
            q.append(node.right)
    return out

Enqueue the root; then repeatedly dequeue a node, visit it, and enqueue its children. Because the queue is FIFO, you always finish an entire level (all the nodes you enqueued earlier) before reaching the next level’s nodes (enqueued later). The queue holds the “frontier” — the nodes seen but not yet visited. That is the precise mechanism of BFS, and Chapter 7 reuses it verbatim to find the shortest number of hops between two nodes in a graph. The tree is the gentle introduction; the graph is the real thing.

Coach’s Note — Depth-first uses a stack (the call stack, implicitly, when you recurse — or an explicit stack if you write it as a loop). Breadth-first uses a queue. That stack-vs-queue distinction is not a detail; it is the difference between “dive deep” and “spread wide,” and it is the same distinction whether you’re walking a tree, a graph, a file system, or a web crawler. When you understand why level-order must use a queue and in-order naturally uses a stack, you understand something that transfers everywhere. Chapter 4 was not busywork. This is where it pays.

6.6 — Balance: Why It’s O(log n) — and When It Isn’t

Now the honest accounting, the Phase 1 soul of the chapter. We have been saying “O(log n)” for search, insert, and delete. That is not quite true. The truthful statement is:

Search, insert, and delete on a BST are O(height).

O(log n) is only what you get when the tree is balanced — when height ≈ log₂(n). And whether the tree is balanced depends entirely on the order the keys were inserted in, which is data you often don’t control.

Here is the catastrophe. Insert keys in sorted order — 1, 2, 3, 4, 5 — into a naive BST. Every new key is larger than everything already there, so it goes right, right, right, right… and you get this:

    insert 1, 2, 3, 4, 5 in order:

    (1)
       \
        (2)
           \
            (3)
               \
                (4)
                   \
                    (5)      <- height = 4 = n-1. This is a linked list.

The tree has degenerated into a linked list with extra steps. Its height is n - 1, not log n. Every search walks the whole chain: O(n). You built a “search tree” that searches no faster than the linked list of Chapter 3 — and slower in wall-clock time, because of the pointer-chasing overhead. The ordering invariant still holds perfectly; the tree is correct. It is just shaped wrong, and shape is cost.

Contrast with a balanced tree of the same n. A balanced binary tree of n nodes has height ≈ log₂(n), because each level holds up to twice as many nodes as the level above (1, 2, 4, 8, …), so it takes only ~log₂(n) levels to hold n nodes. With n = 1,000,000, log₂(n) ≈ 20. So:

Same keys, same structure, same correct code. The balanced tree is fifty thousand times faster to search. The only difference is the shape, and the shape was decided by the insert order. Run code/balance_degradation.py and you will measure this yourself: it builds the same 20,000 keys in random order (≈balanced) and in sorted order (degenerate) and times lookups on both. On my machine the degenerate tree was over 400× slower — and the gap widens as n grows.

This is the Phase 1 lesson restated yet again, now in tree form: asymptotics describe the best you can hope for; the actual cost depends on facts the Big-O doesn’t show you — here, the insert order. “BST search is O(log n)” is a half-truth that becomes a lie the moment your data arrives pre-sorted (and real data is often pre-sorted — log files, timestamps, autoincrement IDs, alphabetized names).

Self-balancing trees exist (and you don’t have to build one)

The fix is a tree that rebalances itself as keys are inserted and deleted, so the height stays ≈ log n no matter what order the keys arrive in. These are self-balancing binary search trees, and the two famous families are:

• AVL trees — rigorously balanced (the heights of any node’s two subtrees differ by at most 1). Faster lookups, more rotation work on insert/delete.
• Red-black trees — more loosely balanced, fewer rotations, so faster inserts/deletes at the cost of slightly taller trees. This is what Java’s TreeMap/TreeSet and the C++ std::map/std::set use under the hood.

They keep balance by performing rotations — small, O(1) local rewirings of three or four nodes that reduce height while preserving the ordering invariant — whenever an insert or delete pushes the tree too far out of balance. You will not implement a self-balancing tree in this course; a correct red-black delete is a multi-week project in its own right and well past Phase 1’s scope. But you must know they exist, know why they exist (to guarantee O(log n) against adversarial insert order), and know that the ordered map/set in every serious standard library is one of them. When you reach for Java’s TreeMap or Python’s sortedcontainers, you are reaching for a balanced tree someone else built and balanced — exactly the kind of “choose a structure you understand the cost of, even if you don’t reimplement it” move that is the whole point of this book.

Coach’s Note — “I implemented a BST” and “I implemented a balanced BST” are separated by an order of magnitude of difficulty, and the gap is almost entirely the rebalancing. The honest architect’s move is: build the plain BST by hand (this week’s project) so you understand the shape and the degeneration cost cold, then use a library’s balanced tree in real code rather than reimplementing red-black rotations under deadline. Knowing what the library is doing — and what it costs — is the skill. Reimplementing it from memory is a party trick. Phase 1 builds the understanding; it does not ask you to out-engineer the standard library.

6.7 — The Cost Table

Here is the BST’s complete cost profile, the next row in the master cost table you’ve been building since Chapter 2. Note the two columns: the balanced case (what you get with a self-balancing tree or lucky insert order) and the worst case (degenerate, from §6.6).

Read this as a shape, not a list of facts. The BST is good at everything that follows the structure — anything that’s “walk down one path” or “walk in sorted order” is cheap. Its weakness is that every cost is gated on the height, so a bad shape (degenerate) turns every O(log n) into O(n) at once. That single vulnerability is the entire reason self-balancing trees exist, and it is why you should reach for a balanced tree (a library’s) when worst-case latency matters and you can’t control insert order.

The two rows that don’t exist in the hash table’s profile — range query and predecessor/successor — are the BST’s reason for living. A hash table cannot do them at all without scanning everything. We turn to that comparison next.

6.8 — Tree vs Hash Table: The Decision a Database Makes

This is the section the whole chapter was built to reach. You now have two structures that both do fast lookup: the hash table (Chapter 5) and the BST (this chapter). When do you choose which? This is a real architectural decision, and you will face the exact same decision, in different clothes, when you choose a database index in Phase 2.

Lay them side by side:

The pattern is stark. For raw membership with no ordering needs, the hash table wins — O(1) beats O(log n), full stop, and that’s most lookups in most programs. The moment you need order — sorted iteration, min/max, predecessor/successor, or range queries — the hash table can’t help and the tree is the only tool. The tree gives you order; the hash gives you raw speed. That is the tradeoff, and naming it is the architect’s job.

The one-sentence rule to carry forever:

Hash table for membership; ordered tree for order. If you’ll ever ask “what’s between X and Y?”, “what’s the smallest?”, or “give it to me sorted,” you need a tree. If you only ever ask “is X here?”, you need a hash.

This is literally the database index decision

Here is the forward link that makes this chapter matter for the rest of the book. In Phase 2, when you put your data in SQLite (Ch 11) and Postgres (Ch 12), you will create indexes to make queries fast. And a database index is exactly one of these two structures, chosen by you, for the same reasons you just learned:

• A hash index gives O(1) lookup for WHERE id = 42 (exact-match equality) — and is useless for WHERE id BETWEEN 10 AND 20 or ORDER BY id, because, like every hash table, it threw the order away.
• A B-tree index (the default in Postgres, SQLite, MySQL — a tree, balanced, fanned out to many children per node for disk efficiency) gives O(log n) lookup and supports BETWEEN, <, >, ORDER BY, and MIN/MAX — because, like every search tree, it keeps the keys in sorted order.

When you type CREATE INDEX ... USING hash versus the default B-tree in Postgres, you are making the precise tree-vs-hash decision of this section, on a structure the database built for you. The B-tree is a balanced search tree adapted for disk (wide nodes, so each disk read fetches many keys — addressing the cache/disk-locality weakness of §6.3 head-on). Everything you learned this week about why a tree supports range queries and a hash doesn’t is exactly the knowledge that lets you choose the right index in Week 11. The database hides the tree; you, the architect, will see through it — the same X-ray-vision move you made on Python’s list in Chapter 2.

Coach’s Note — This is the thesis of the entire book in one decision. AI builds what you specify; the architect decides what’s worth building — and what it costs. An agent can write CREATE INDEX for you in two seconds. It cannot tell you whether this table, with these query patterns, wants a hash index or a B-tree — because that depends on which queries your application actually runs, which is a fact about your problem that lives in your head, not the model’s. Choosing the index is choosing tree-vs-hash, and choosing tree-vs-hash is this chapter. You are, right now, learning the thing that makes you more than a person who can prompt for a CREATE INDEX statement. Hard P6 makes you write that decision down as a memo. Take it seriously; it’s the architect’s actual work.

6.9 — Common Bugs

The bugs that bite when you build and use trees.

Bug: Forgetting to reassign the link after a recursive insert/delete. You recurse into a subtree but throw away the returned subtree root, so the structure never actually changes. Example: self._insert(node.left, key) — return value discarded. The new node was created and immediately orphaned; the tree is unchanged and the key seems to vanish. Fix: Always node.left = self._insert(node.left, key). The recursion returns the new subtree; wire it back into the parent. This is the reassign-the-link pattern from §6.4 — the single most important habit in tree code.

Bug: Botching delete Case 3 by trying to move nodes instead of copying a key. Example: Promoting the left child and trying to hang the right subtree somewhere — you end up violating the ordering invariant or dropping a whole subtree. Fix: Copy the in-order successor’s key into the node, then delete the successor from the right subtree. Don’t rewire pointers; copy one key. The successor has no left child, so its own deletion is the easy Case 1/2.

Bug: Off-by-one (or off-by-direction) in the comparison: using <= where the invariant says <, so equal keys leak into the wrong subtree. Example: if key <= node.key: go left — now a duplicate of node.key goes left, but search for it goes… where? You’ve created two valid homes for one key and broken lookup. Fix: Decide your duplicate policy explicitly (this course: ignore duplicates — set semantics). Use strict < and >, with the equal case handled separately as “found / already present.”

Bug: Recursion depth blowing the stack on a degenerate tree. Example: A recursive in-order on a tree built from a million sorted inserts (height ≈ a million) crashes with RecursionError: maximum recursion depth exceeded. Fix: Recognize that recursion depth = tree height, and a degenerate tree’s height is n. Either use a balanced tree (so height is log n), raise the recursion limit and accept the risk, or write the traversal iteratively with an explicit stack/queue (as code/balance_degradation.py does for height). This is the §6.1 stack-frame cost coming due.

Bug: Assuming a hand-rolled BST gives O(log n). It gives O(height), and you didn’t control the height. Example: Building an “index” by inserting already-sorted records, then being baffled that lookups are O(n) in production. (They arrived sorted because they were a sorted export.) Fix: A plain BST is only O(log n) on lucky/random insert order. For a worst-case guarantee, use a self-balancing tree (a library’s TreeMap, sortedcontainers, etc.). Never assume balance you didn’t enforce.

Bug: Reaching for a tree when a hash table was the right tool, or vice versa. Example: Using a sorted tree for a set you only ever test membership on (you paid O(log n) and cache misses for ordering you never use). Or using a hash set and then writing an O(n log n) “sort the keys” step every render because you actually needed order. Fix: Apply the §6.8 rule. Only ever ask “is X here?” → hash. Ever ask “sorted? between? min? next?” → tree. Choosing wrong isn’t a crash; it’s a silent, permanent tax on every operation.

6.10 — Reps

Open the exercises for the full set. This week’s reps build the muscles the project demands: thinking recursively about trees, writing all three traversals cold, hand-tracing the three delete cases, and feeling the balanced-vs-degenerate cost gap in real timings. AI stays OFF — Phase 1. You cannot direct an agent to choose a tree later if you have never built one and watched it degrade with your own eyes.

A preview:

• Rep 1 — Draw a BST from a given insert sequence; then draw the same keys inserted sorted, and compare heights.
• Rep 4 — Write all three depth-first traversals from scratch — in-order, pre-order, post-order — and predict each output before running.
• Rep 7 — Hand-trace all three delete cases on paper, then verify against bst_demo.py.
• Rep 10 — Implement keys_between(lo, hi) and reason about why it’s O(log n + k) on a balanced tree.
• Rep 11 — Measure balanced vs sorted-insert lookup time and explain the gap with §6.6.

Do every one. The reps are the conditioning; the project is the game.

6.11 — This Week’s Project

You’re ready for Project 6 — A Searchable Tree, in Project 6.

You will build a binary search tree from scratch: insert, contains, and delete handling all three cases, plus the in-order traversal that yields keys in sorted order — with tests that prove every claim, including each delete case. The Medium tier adds min, max, height, and a range query keys_between(lo, hi), and makes you measure the lookup-time gap between a balanced tree and a deliberately degenerate (sorted-insert) one — and explain why the unbalanced one rots to O(n). The Hard tier is the memo that is the heart of the week: a written comparison of your BST against your HashMap from P5 — for which workloads is the tree the right tool (ordered iteration, range, predecessor/successor) and for which is the hash right (raw membership) — tied explicitly to the database index decision you’ll face in Phase 2.

Like every Phase 1 project, it ends in a written deliverable about cost and the right tool. The code is the craft; the memo is the architecture.

6.12 — Coach’s Final Word for Week 6

This week you met the structure that recursion was made for. You learned the vocabulary — root, leaf, height, subtree — and the one rule that turns a tree into a search tree: smaller left, larger right, at every node. You wrote insert and search as short recursive walks, and you wrestled delete down to three honest cases with the in-order-successor trick that makes the hard case easy. You learned that in-order traversal hands you your keys sorted, for free — the BST’s whole reason to exist over a hash table. And you learned the dark truth that “O(log n)” is really “O(height),” that a sorted-insert tree rots into a linked list, and that self-balancing trees exist to guarantee the balance you can’t.

Most of all, you learned the decision: hash for membership, tree for order — the same decision a database makes when it chooses an index, which is where this all goes in Phase 2.

If the three delete cases still feel slippery: that’s the gap. Draw them — three nodes, three pictures, on paper — until the successor trick is obvious instead of memorized. Close it.

The psalmist’s tree is planted by streams of water and yields its fruit in its season — rooted, ordered, fruitful because it is connected to its source. The vine holds its branches, and the branches bear fruit only while they abide. A binary search tree is a small, mechanical echo of that picture: every node holds its place only through an unbroken chain back to the root, and the whole structure bears its fruit — sorted order, fast search, range queries — only because that connection holds. Build trees that abide. Sever no branch carelessly. And when you delete a node, remember you are tending a living shape, not blanking a slot.

See you on Monday.

Up next: Read the exercises and complete every rep. Then open Project 6 and build your searchable tree. After that, Chapter 7 — graphs and the shape of connection, where the queue-driven breadth-first search you wrote for level-order this week becomes the engine for finding the shortest path between any two nodes.

Previously: Chapter 5 — hash tables: the magic of O(1) membership, and the fine print that throws away all order.