Quadtree — Part 2: Internals & Implementation

maang.io System Design Series

What is this?

Back to the dispatch office and its wall map full of pushpins. In Part 1 we learned the habit — cut a crowded district into four, recurse where it's still crowded. Now we're going to watch the clerk's hands: exactly what happens to the map when a new pin arrives, how the "cut into four" move re-files the existing pins, and how someone standing at the map answers "show me every pin within this rectangle" or "find the pin nearest to here" without scanning the whole wall.

We'll implement the PR (point-region) quadtree from Part 1 — equal-quarter splits, points in capacity-bounded leaves — because it's the one that powers find-nearby, collision detection, and mapping. By the end you'll be able to reason about its memory layout, its write and read paths, its exact cost with numbers, and the one input pattern that quietly destroys it.

The one-line idea: Every operation is "which of my four quadrants contains this point/rectangle?" applied recursively. Insert walks down to a leaf and splits it into four equal children when it overflows; a range query prunes any subtree whose box misses the query rectangle; and the whole thing is fast only as long as points are spread out enough that the tree stays shallow — which is exactly the assumption the degenerate case violates.