AlgoMaster Logo

Quad Trees

Medium Priority17 min readUpdated October 25, 2026
AI Mock Interview

Practice this topic in a realistic system design interview

Premium Video

This video is available to premium subscribers only

Unlock Full Access

Finding things near a point is a common system design problem. A maps app needs nearby restaurants. A ride-sharing app needs nearby drivers. A game needs nearby objects. Checking every point works for a few thousand points, but not for millions.

A quadtree helps by dividing a map into smaller and smaller regions, but only where the data is dense. During a search, it can skip whole regions that can't contain a match.

In this chapter, we'll learn what a quadtree is, how it divides a map into smaller regions based on where the data actually is, how it answers nearby searches, and where systems use it in practice.

Loading simulation...

1. The Problem

Suppose you're building an app that shows nearby places, like restaurants, cafes, and gas stations. You have 100 million places around the world, each with a latitude and longitude. When a user opens the app, you need to quickly find the places closest to them.

One approach is to divide the map into a fixed grid of equal-sized cells. Each place is assigned to the cell it falls into. When a user searches, you check their cell and the surrounding cells.

This works, but there's a problem. Places are not distributed evenly. A cell in downtown Manhattan might contain thousands of places. But a cell of the same size in the middle of a desert might contain none.

  • If we make the cells too large, searches in crowded cities return too many places that we then have to filter.
  • If we make them too small, we end up with lots of empty cells, and searches in rural areas may need to cover many cells to find nearby places.

Ideally, we want a grid that adapts to the data, with smaller cells in dense areas and larger cells where places are spread out.

2. What Is a Quadtree?

Premium Content

This content is for premium members only.