Recursion & Trees

Welcome to Recursion & Trees, the seventh module — which begins by finding the limit of Module 6’s best idea. Hashing was a genuine triumph: a dict finds a zone by id in constant time whether it holds ten entries or ten million, and it beat a list scan by 19.2x on the real month. But ask it a slightly different question — give me every trip between 08:00 and 09:00 — and it collapses. It cannot help at all. A hash table computes a slot from a key precisely by scattering neighbouring keys as far apart as possible, so nothing about where 08:00 landed tells you where 08:01 lives. Answering a range means checking every key, and you are back to the scan you paid an index to avoid.

What a range query needs is the one property hashing deliberately destroys: order. Order is what lets you rule out half the data with a single comparison, bracket a window with two probes, merge two sorted streams by always taking the smaller head, and skip a block of a file because its largest value is smaller than what you’re looking for. Ordered data lives in trees — and in their flat, cache-friendly cousin, the sorted array — which is why every real database ships a B-tree index rather than only a hash. Trees are also recursive by nature: a tree is a node holding smaller trees, so the code that walks one is naturally recursive too. That is why this module teaches recursion first.

Across five lessons you’ll earn each idea on CityFlow’s real taxi data: recursion that matches the shape of the data without blowing the stack, binary search that finds a timestamp in log time, an external sort that orders more rows than fit in memory, and the min/max statistics already sitting in the Parquet file that let you skip whole row groups. Then you’ll assemble them into a time-range index that answers “trips 8-9am” without ever loading the month. Start with Lesson 1, where recursion turns out to be slower than a loop — and worth reaching for anyway, for reasons that have nothing to do with speed.