Chapter 6 — Reps

Conditioning, not grading. Python reps this week, all about trees, recursion, traversals, and the cost of balance.

Ground rules:

1. Type every line yourself. No copy-paste. With trees especially, your fingers learn the reassign-the-link pattern (node.left = recurse(...)) only by typing it until it’s automatic.
2. Draw before you code. Trees are the one structure where a five-second sketch on paper saves an hour of debugging. Every rep that touches structure: draw the tree first.
3. Predict, then run. Write down the expected output (or the tree’s shape, or the traversal sequence) before you run. The gap between your prediction and reality is the lesson.
4. AI stays OFF. Phase 1. You cannot direct an agent to choose a tree index later if you have never built a tree and watched it degrade with your own eyes. Build it.
5. Measure honestly. When a rep says “time it,” use time.perf_counter(), run each measurement a few times, and report the median — the first run is cold.

These reps assume Python 3.10+ on your own machine (Appendix A). The chapter’s code/ folder has runnable demos referenced below.

Reps 1–3: Vocabulary and Shape

Rep 1 — Draw it, then measure the height

On paper, draw the BST you get by inserting these keys in this order into an empty tree:

50, 30, 70, 20, 40, 60, 80, 10

Then draw the BST you get by inserting the same keys in sorted order:

10, 20, 30, 40, 50, 60, 70, 80

For each tree, write down: the root, the leaves, the height, and the depth of the key 40. Predict which tree is taller and by how much. The first should be a tidy, roughly-balanced tree of height ~3; the second should be a degenerate right-leaning chain of height 7 (a linked list). This is §6.6 in pencil before you ever measure it in code.

Rep 2 — The vocabulary, cold

Close the book. On paper, define each term in one clause: root, node, child, parent, leaf, edge, subtree, depth, height (of a node), height (of the tree). Then open §6.2 and check. For the two you’re most likely to confuse — depth vs height — write one sentence on how they’re measured from opposite ends (depth counts up to the root; height counts down to the deepest leaf). Any term you got wrong, write its definition three times.

Rep 3 — Verify the ordering invariant

Here is a tree drawn as nested tuples (key, left, right), with None for empty:

tree = (50,
        (30, (20, None, None), (40, None, None)),
        (70, (65, None, None), (80, None, None)))

Is this a valid BST? Check the ordering invariant at every node by hand. Then write a function that checks it for you — but be careful, because the naive check is a classic bug:

def is_bst(node, low=float("-inf"), high=float("inf")):
    """A node is valid if its key is in (low, high) AND both subtrees are valid
    within the tightened bounds. Checking only parent-vs-child is NOT enough --
    every key in the left subtree must be < this key, not just the immediate child."""
    if node is None:
        return True
    key, left, right = node
    if not (low < key < high):
        return False
    return is_bst(left, low, key) and is_bst(right, key, high)

Run it on the tree above (valid). Then mutate 65 to 55 and re-run — still valid? Now mutate 65 to 45 and re-run. The 45 is a direct child of 70 and 45 < 70, so a naive parent-child check would pass it — but 45 belongs in 50’s left subtree, so the tree is invalid. Confirm is_bst catches it. Write one sentence on why the bounds-passing version is correct and the parent-child-only version is not.

Reps 4–6: Traversals

Rep 4 — All three depth-first traversals, from scratch

Build this tree by hand (use the Node class from code/traversals.py or your own):

            (8)
           /   \
        (3)    (10)
        / \       \
     (1) (6)     (14)
         / \      /
       (4) (7)  (13)

Write in_order, pre_order, and post_order. Predict each output sequence on paper first. Then run and check. In-order must come out sorted (1 3 4 6 7 8 10 13 14); if it doesn’t, your tree is drawn wrong or your traversal is wrong — find which. Write one sentence on what changed between the three functions (only the position of the “visit me” line).

Rep 5 — Level-order with a queue

Add level_order to the same tree, using collections.deque as your queue (§6.5). Predict the output before running — it should come out by rows: 8, then 3 10, then 1 6 14, then 4 7 13. Then answer in writing: why can’t you write level-order with simple recursion the way you wrote the other three? (Because recursion is depth-first — it dives down one branch fully before backing up — and you need to go across a level before going down. The queue holds the frontier.)

Rep 6 — Recover the tree from traversals

A pre-order traversal of a BST is 50 30 20 40 70 60 80. Without being told the tree’s shape, reconstruct it. Hint: pre-order visits the root first, so 50 is the root; then every following key less than 50 (30 20 40) is the left subtree and the rest (70 60 80) is the right, and you recurse. Draw the tree. Then verify by running your in_order on it — it must produce the sorted sequence 20 30 40 50 60 70 80. This rep proves you understand why pre-order is the traversal used to serialize and rebuild a tree (§6.5).

Reps 7–9: Insert, Search, and the Three Delete Cases

Rep 7 — Hand-trace the three delete cases

Start from this tree (insert order 50, 30, 70, 20, 40, 60, 80, 65):

            (50)
           /    \
        (30)    (70)
        / \     /  \
     (20)(40)(60)  (80)
              \
              (65)

On paper, perform and draw the result of each deletion on the original tree (three separate exercises, each from the original):

1. Delete 20 — a leaf (Case 1). Draw the result.
2. Delete 60 — one child, 65 (Case 2). Draw the result.
3. Delete 50 — two children, the root (Case 3). The in-order successor is the smallest key in the right subtree. Find it, copy it into the root, delete the old copy. Draw the result, and confirm in-order is still sorted.

Then run code/bst_demo.py (or build the tree and call delete) and confirm your hand-drawn answers match. Any mismatch is a delete misunderstanding — find it now, not in the project.

Rep 8 — Insert, the reassign-the-link pattern

Type out the recursive insert from §6.4 into a real BST class. Then deliberately introduce the most common bug: change

node.left, inserted = self._insert(node.left, key)

to

self._insert(node.left, key)            # BUG: return value discarded
inserted = True

Insert 50, 30, 70 and print the in-order traversal. Watch keys vanish (only the root survives). Then fix it back and watch them reappear. Write one sentence on why discarding the return value orphans the new node (§6.9). This is the single most important habit in tree code; break it once on purpose so you never break it by accident.

Rep 9 — contains, iterative and recursive

Write contains(key) two ways: once iteratively (the while node is not None loop from §6.4) and once recursively. Confirm both give the same answers on a tree of your choosing (test a key that’s present, one that’s absent-but-smaller-than-everything, one that’s absent-but-larger). Then answer in writing: which would you ship, and why? (The iterative one — same O(height), no risk of a RecursionError on a degenerate tree, no stack-frame overhead. Recursion is the right tool for traversals that must visit every node; for a single root-to-target walk, the loop is cleaner and safer — §6.9.)

Reps 10–11: Range Queries and the Cost of Balance

Rep 10 — keys_between(lo, hi)

Add a method that returns all keys in the inclusive range [lo, hi], in sorted order. The naive version is “in-order traverse everything, filter” — O(n). Do better: prune subtrees you don’t need to visit.

def keys_between(self, lo, hi):
    out = []
    self._between(self._root, lo, hi, out)
    return out

def _between(self, node, lo, hi, out):
    if node is None:
        return
    # Only recurse left if there could be keys >= lo over there.
    if node.key > lo:
        self._between(node.left, lo, hi, out)
    # Include this key if it's in range.
    if lo <= node.key <= hi:
        out.append(node.key)
    # Only recurse right if there could be keys <= hi over there.
    if node.key < hi:
        self._between(node.right, lo, hi, out)

Build a tree with keys 0..99 (insert them shuffled so it’s balanced) and call keys_between(30, 40). Confirm you get [30, 31, ..., 40], sorted. Then explain in writing why this is O(log n + k) on a balanced tree (where k is the number of results): O(log n) to descend to the range, then O(k) to walk the matching keys, and the pruning (if node.key > lo, if node.key < hi) skips the subtrees entirely outside the range. This is the operation a hash table cannot do — the whole reason a database uses a B-tree index for WHERE x BETWEEN lo AND hi (§6.8).

Rep 11 — Measure balanced vs degenerate

Run code/balance_degradation.py. It builds the same 20,000 keys two ways — random insert order (≈balanced) and sorted insert order (degenerate) — reports each tree’s height, and times a batch of lookups on each. Predict, in writing, before running: roughly how tall will each tree be, and roughly how much slower will the degenerate one be? (Balanced height ≈ log₂(20000) ≈ 15-ish, plus the slack of random insertion, so 30-ish. Degenerate height = 19,999. Expect the degenerate tree to be hundreds of times slower.)

Then run it. Were you close on the heights? On the slowdown factor? Write two sentences relating the numbers to §6.6: the cost is O(height), not O(log n); the only thing that changed between the two trees was the insert order, and insert order decided the shape, and shape is cost. Finish with one sentence naming the fix (a self-balancing tree — AVL or red-black — guarantees height ≈ log n regardless of insert order).

Done? One Last Thing.

From scratch, no looking — write a minimal BST class with insert, contains, in_order (sorted output), and delete handling all three cases. No starter, no peeking at §6.4. Then prove it cold with this driver:

bst = BST()
for k in [50, 30, 70, 20, 40, 60, 80, 35, 45]:
    bst.insert(k)

assert list(bst.in_order()) == sorted([50, 30, 70, 20, 40, 60, 80, 35, 45])
assert bst.contains(40) and not bst.contains(41)

bst.delete(20)   # leaf (Case 1)
bst.delete(30)   # one child (Case 2)
bst.delete(50)   # two children, root (Case 3)

assert list(bst.in_order()) == [35, 40, 45, 60, 70, 80]   # still sorted!
print("PASS — BST cold, all three delete cases, in-order stays sorted")

If every assertion passes — especially that in-order stays sorted after deleting the two-child root — you have the move, and the Normal tier of the project is already in your hands. If a delete breaks the sorted-ness, you violated the ordering invariant in Case 3; re-read §6.4 and draw the successor swap until it’s obvious.

Up next: Project 6 — Project 6: A Searchable Tree.