Quadtree
maang.io System Design Series
A quadtree recursively splits a 2D region into four quadrants, subdividing only where the data is dense. That structure turns "find everything near this point" and range queries from a full scan into a logarithmic descent — which is why quadtrees power maps, "nearby" search, collision detection, and image compression.
This deep dive comes in three parts:
- Foundations & Core Concepts — recursive subdivision, node capacity, and point vs region quadtrees.
- Internals — range and nearest-neighbour queries, the skew/degenerate cases, and comparisons to k-d trees and R-trees, with worked numbers.
- Interview — Staff/Principal Q&A: choosing a spatial index and the trade-offs vs geohashing.