Imagine you’re building a map application. Your database holds millions of restaurants, gas stations, and landmarks, each with latitude and longitude. A user taps the screen and asks: “What’s around me?”

This is exactly where a quadtree shines. But before explaining it, let’s look at the most straightforward approach: calculate the distance to every single point, keep the close ones, discard the far ones.

It works. It’s just slow.

A thousand points? Fine. A million points? That’s a million distance calculations per query. The user swipes the map, it moves, triggering several queries per second. Your phone’s CPU explodes on the spot.

The Wisdom of Finding Keys

Think about it. If you lost your keys in a large house, how would you search?

You wouldn’t start at the entrance and scan every inch of carpet. You’d divide the house into zones: living room, bedroom, kitchen, bathroom. Then you’d think: “Where did I go?” Didn’t visit the kitchen? Skip it. Never entered the bathroom? No need to look. Focus your energy on the areas you actually spent time in.

That’s exactly what a quadtree does, except for two-dimensional space.

Here’s how it works: Take a rectangular region and slice it into four equal parts—top-left, top-right, bottom-left, bottom-right. If a quadrant has too many points, slice it again into four. When does it stop? When each cell has few enough points, you stop subdividing.

The result: dense areas get small cells, sparse areas get large cells. The tree structure adapts automatically to your data distribution.

Brute Force vs Quadtree

Let’s feel the difference.

Brute force works like this: no matter which region you’re asking about, it traverses every single point. A point in the top-right corner of the map, completely unrelated to your query about the bottom-left? Still gets checked. Massive waste of effort.

The quadtree approach: First check if the cell’s range intersects with your query region. No intersection? Skip that cell and everything beneath it. Intersection? Drill down, filtering layer by layer.

The result: instead of checking a million points, you might check only a few thousand. Query time drops from seconds to milliseconds.

How to Build a Quadtree

The construction process is intuitive:

  1. Start with the entire map as one big square
  2. Add a point to it
  3. Too many points in the square? Split into four, redistribute points to their quadrants
  4. Repeat steps 2-3

What should the capacity limit be? Common practice is between 4 and 16. Set it low: deeper tree, more cells, faster queries but more memory. Set it high: shallower tree, less memory but more linear scanning within cells. Tune based on your data distribution and query patterns.

One detail worth mentioning: a quadtree’s split lines are fixed, always at the midpoint. This differs from KD-trees, which decide where to split based on actual point positions. The benefit of quadtrees: predictable split locations. The downside: if points are unevenly distributed, some cells get crowded while others stay empty.

Range Query: Finding All Points in a Region

This is the most common quadtree operation. Given a rectangle, find all points inside.

The algorithm logic is recursive:

def range_query(node, rect):
    if node.region doesn't intersect rect:
        return []  # Prune entire branch

    if node is a leaf:
        return [p for p in node.points if p is inside rect]

    result = []
    for child in node.children:
        result += range_query(child, rect)
    return result

The key is the first check: if the current cell’s range doesn’t touch the query rectangle at all, ignore every point beneath it. This pruning step saves massive computation.

Nearest Neighbor Query: Finding the Closest Point

Sometimes you don’t know what search radius to use. You want to ask: “Where’s the closest point to me?”

The algorithm’s approach:

  1. Maintain a “current nearest distance,” initially infinity
  2. Traverse tree nodes, updating nearest distance whenever you find a point
  3. Before entering a child node, check: could this child’s range possibly contain a point closer than the current nearest? If not, skip the entire subtree

Here’s an optimization trick: visit child nodes sorted by distance. Query the quadrant closest to your query point first—this finds a “decent” candidate faster, letting you more aggressively prune other branches.

Ideally, nearest neighbor queries approach O(log n) time complexity. With a million points, you can find the closest one in about a dozen comparisons.

Collision Detection: A Game Engine’s Best Friend

Games constantly need to check which objects have collided. With n objects, brute force checks every pair—O(n²) complexity. 100 objects means nearly 5,000 checks. 1,000 objects means nearly 500,000 checks.

A quadtree optimizes dramatically: rebuild the tree each frame, then for each object, query only its nearby region. Distant objects never make the candidate list.

In real game engines, quadtrees (or their 3D cousin, octrees) handle the “broad phase”: quickly identify potentially colliding pairs, then use precise geometric calculations for the “narrow phase.”

Image Compression: Another Face of Quadtrees

Quadtrees handle not just point data but continuous regions, like images.

The idea: look at an image region. If the pixels’ colors are similar enough (differences below a threshold), represent the whole block with an average value. If differences are too large, split into four and recurse.

The result: uniform areas (blue sky, white walls) get stored as large blocks. Complex areas (edges, textures) get split into small blocks to preserve detail.

This resembles JPEG’s philosophy: save space in low-information areas, preserve quality in high-information areas. Of course, real JPEG uses discrete cosine transforms and entropy encoding—far more complex than quadtrees—but the core idea is the same: don’t apply effort uniformly. Spend resources where they matter.

The Quadtree Family

Quadtrees belong to a family of spatial partitioning data structures. Meet the relatives:

The octree is the 3D version of a quadtree, splitting into eight parts each time. Game engines and volume rendering use it frequently. The KD-tree splits differently—one dimension at a time. First along the x-axis, then y-axis, alternating. Split positions can flexibly adjust based on data distribution.

Then there’s the R-tree, which packages nearby objects into bounding boxes, nested layer by layer. PostGIS uses its variant (GiST index), perfect for storing non-point data like polygons and line segments.

Each has its use case. Quadtrees win on simplicity—fixed split positions make implementation and debugging easy. KD-trees may be more balanced on unevenly distributed data. R-trees are more flexible for non-point data (regions, line segments).

When to Use a Quadtree

To summarize, quadtrees suit these scenarios:

  1. Frequent spatial queries—“what’s in this region?” or “what’s closest to this point?”
  2. Relatively uniform data distribution—not all points crammed onto one line
  3. Mostly static data, or infrequent updates where rebuilding the tree is acceptable
  4. Queries with strong locality—each query covers a small area

Map applications, game physics, spatial databases—these all fit.

If your data updates extremely frequently, or queries often cover large ranges, consider alternatives. No silver bullet. Use the right tool for the job.

Frequently Asked Questions

Q: What’s the difference between a quadtree and a hash table? When should I use each?

A: Hash tables are for exact lookups (give me the record with key X). Quadtrees are for range lookups (give me records within 1km of coordinates (x, y)). If you’re querying “equals,” use a hash table. If you’re querying “nearby,” use a quadtree.

Q: What’s the actual time complexity of quadtree queries?

A: Ideally (uniformly distributed data), point queries and range queries are both O(log n). But worst case (all points on a single line) can degrade to O(n). In practice, spatial data tends to cluster, so quadtrees perform much better than brute force.

Q: What about dynamic updates? Rebuilding the tree every time is too slow.

A: Several approaches exist. Lazy updates: mark deletions, batch rebuild. Incremental updates: rebuild only affected branches. Or use a structure better suited for dynamic data, like an R-tree, whose split and merge operations are more localized.