Rung 26
Trees and heaps
Structures that are fast because of their shape.
Best attempted after 25. Recursion. Nothing stops you trying this now — the gate will tell you if you were right.
The gate
Implement a binary search tree with insert, search, and an in-order traversal that emits the keys in sorted order. Then insert already-sorted data, show the tree has degenerated into a list, and measure search slowing from logarithmic to linear as it does.
Nobody checks this but you. Do it honestly and the rungs above hold; do it loosely and they will not, somewhere further up where the cause is much harder to find.
Rung 18's structures were flat. A tree branches, and the branching is what makes it fast: at each step you discard half of what remains, so a million items are reachable in about twenty comparisons.
That "about twenty" is rung 9 returning. Twenty halvings of a million is
log₂(1,000,000) ≈ 20. The structure's speed is a logarithm.
Why this is on the ladder
Because rung 35's graphs and DAGs are this idea with the restrictions lifted, and a computation graph — the thing an autodiff system walks to apply rung 22's chain rule — is exactly such a structure.
And because this is the cleanest demonstration that shape determines cost. The same code, the same operations, and a hundredfold difference in speed depending only on the order things arrived.
Do this
Build the binary search tree: every left descendant smaller, every right descendant larger. Insert, search, and an in-order traversal — which, if your invariant holds, emits the keys sorted. That sorted output is a free correctness check on the whole structure; use it.
Write the traversal recursively. It is three lines and it is rung 25 doing exactly what rung 25 promised.
Now break it deliberately. Insert 1, 2, 3, …, n in order. Every key goes right;
there is no branching; you have built a linked list wearing a tree's clothes.
Measure search on the balanced case and the degenerate case across several sizes,
and watch log n and n separate on the plot — a plot best read on rung 10's log
axis.
Where people get stuck
Testing only on random input, where trees are balanced by luck and the worst case never appears. Sorted input is not exotic; it is one of the most common shapes real data arrives in, which is what makes this failure mode a practical concern rather than a curiosity.
Deletion is fiddlier than insertion — the two-child case needs a successor promoted. If it is fighting you, get insert, search and traversal solid first; they carry the rung.