What is a Quadtree and How Does It Work?

Definition
A quadtree recursively divides 2D space into four quadrants. Each node either contains points directly (leaf) or has four children (internal). Points concentrate where data is dense; empty regions remain undivided. This adaptive structure efficiently indexes non-uniform spatial data.
Recursive Subdivision
Start with a bounding box covering all possible points. When a leaf node exceeds capacity (typically 100 to 1000 points), split it into four equal quadrants: NW, NE, SW, SE. Each quadrant becomes a child node. Redistribute points to the appropriate children. Repeat recursively.
Empty quadrants need not be stored. A city with one populated corner has deep subdivisions there but shallow or absent nodes elsewhere. The tree adapts to data density automatically.
Query Algorithm
To find points within a region, start at the root. Check if the query region intersects this node. If not, skip entirely. If yes, check if this is a leaf: search its points. If internal, recursively check children that intersect the query region.
Query complexity depends on tree depth and data distribution. For uniformly distributed data, range queries are O(sqrt(n) + k) where k is result count. For clustered data, performance varies with cluster density. Dense areas have deeper trees and longer traversals.
Insert and Update
Insert traverses from root to the appropriate leaf, then adds the point. If the leaf overflows, split it. Updates for moving points: remove from old location, insert at new location. Frequent moves can cause tree imbalance if not rebalanced periodically.
💡 Key Insight: Quadtrees adapt subdivision to data density. Dense areas get fine-grained cells; sparse areas stay coarse. This is more efficient than fixed grids for non-uniform distributions like city location data.

💡 Key Takeaways

✓Quadtree divides space into four quadrants recursively; adapts to data density

✓Leaf nodes hold points up to capacity; overflow triggers split into 4 children

✓Query traverses only nodes that intersect search region; prunes irrelevant branches

✓Range query complexity: O(sqrt(n) + k) for uniform data, varies for clustered data

✓Empty quadrants need not exist; tree structure matches actual data distribution

📌 Interview Tips

1Explain adaptive subdivision: a city map has deep nodes in downtown, shallow or missing nodes in empty areas

2Walk through range query: start at root, prune non-intersecting children, recurse into intersecting ones

3Compare to fixed grid: quadtree avoids wasting cells on empty ocean while providing detail in dense cities

← Back to Quadtree & Spatial Indexing Overview