Skip to content
Algorithm Atlas
Data StructuresAll categories
CoreSource checked

Quadtree

Indexes 2D space by recursively subdividing regions into four quadrants.

Explore relationshipsOpen constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category
Data Structures
Difficulty
Intermediate
Family
Spatial Index
Tier
Core
Status
Verified
Review
Source Checked
Sources
1
Formulas
0
Relationships
4
Code example
Ready
Visualization
Ready

Overview

A Quadtree stores points or objects in a tree of square or rectangular regions, splitting crowded regions into four children.

Core Concepts

spatial subdivisionquadranttree noderange query

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(log n)

Average

O(log n) average query

Worst

O(n)

Space

O(n)

When to Use

  • Use when 2D spatial queries need to skip large empty regions.
  • Use when 2D collision culling is a central requirement.

When Not to Use

  • Avoid when objects are high-dimensional or not spatially organized.
  • Avoid when a simpler array, map, or list already meets the access pattern.

What It Does

  • Partitions 2D space
  • Stores objects by region
  • Supports spatial queries

Use Cases

  • 2D collision culling
  • Map indexing
  • Image region decomposition

Inputs

  • 2D points or bounding boxes
  • Spatial bounds
  • Capacity threshold

Outputs

  • Hierarchical spatial index

Pseudocode

  1. 1.Create a root region
  2. 2.Insert objects into the smallest suitable region
  3. 3.Split a region when it exceeds capacity
  4. 4.Query by visiting only regions that overlap the search area

Canonical Example

Input
points clustered in top-left
Output
top-left quadrant splits again
Explanation
Dense regions get more detailed subdivisions than sparse regions.

Implementation Notes

  • Set maximum depth and capacity thresholds together.
  • Keep update operations small and test invariants after insertions and deletions.
  • Keep a tiny example with known output beside the implementation.
  • Test updates and queries as sequences, not only one operation at a time.

Common Pitfalls

  • Large objects that span many cells can be duplicated or missed without a clear rule.
  • The advertised performance depends on maintaining the structure's invariants.
  • Not defining boundary, empty, or degenerate inputs before implementation.
  • Incorrect updates can leave stale pointers, counts, balance metadata, or cached summaries.

Interactive Mechanism Walkthrough

Graph Frontier & Edge Relaxation

Show a 2D region splitting into four children where points are dense.

Quadtree mechanism walkthrough step 1 of 4suvwxt
Step 1 of 4: Create a root region
data-structure

Notes

Unbalanced distributions can create deep trees unless split depth is capped.

Sources (1)

What each reference supports for this entry.

Handbook of Data Structures and Applications

Book

Data-structures reference for quadtrees, recursive planar subdivision, and spatial indexing.

Explore Next

Good next jumps from the relationship graph, ranked for useful discovery.

Open discoveryOpen map
Alternative tok-d Tree

Data Structures · Core

Quadtrees and k-d trees are spatial partitioning structures with different split rules.

Compare with this
AlternativesR-Tree

Data Structures · Extended

R-trees and quadtrees are spatial indexes with different bounding and subdivision strategies.

Compare with this
Generalized byOctree

Data Structures · Core

Octrees generalize quadtree-style recursive spatial subdivision from two dimensions to three.

Compare with this

Relationships

View full relationship page
Alternative tok-d Tree

Quadtrees and k-d trees are spatial partitioning structures with different split rules.

Related Algorithms

k-d TreeR-Tree

Tags

Data StructureTreeSpatial IndexSpatial Data Structure