A KD-tree, this site's other Spatial entry, splits on the data: every cut is placed at the median of whatever points currently sit in a node, so the tree's depth stays balanced no matter how the points are distributed. A quadtree makes a different bet — it splits on the space instead. Every node covers a rectangular region; once that region holds more points than a fixed capacity, it splits into exactly four equal quadrants (northwest, northeast, southwest, southeast) at the region's own geometric center, regardless of where the points inside it actually fall. The split point is decided before a single point is looked at.
That trade shows up directly in what each structure is good at. A KD-tree's median-based split guarantees balanced depth but can still degrade on query cost when the data doesn't vary along some axis (see its own Pitfalls section). A quadtree's fixed-center split makes each region trivial to compute and identical to reproduce from coordinates alone — useful when regions themselves need to be addressed, not just points — but it has no such guarantee against clustered data at all, which this page's own Pitfalls section measures directly.
Fourteen points, capacity 3 per box. Press Step or Run to insert them one at a time: watch a box split into four equal quadrants — drawn as nested rectangles, not point-to-point lines — the moment a fourth point would land inside an already-full box, with its existing points re-sorted into whichever new quadrant actually contains them. Once every point is placed, the demo switches automatically to a range query for the dashed rectangle: watch it walk the tree, skip (fade out, dashed) any box that doesn't overlap the rectangle at all — sometimes an entire quadrant at once — and mark every point that lands inside it as a match.
Inserting a point starts at the root and walks down: if the current box isn't yet divided and has room under its capacity, the point is simply added to that box's list. If the box is already divided, the point is handed to whichever of the four children's region actually contains it — an O(1) check, since a quadrant boundary is just its parent's midpoint on each axis, no comparison against other points required. The interesting step is what happens when an undivided box is already at capacity: it splits into four new quadrants of exactly half its width and height, its existing points get re-homed into whichever new quadrant contains each of them, and only then does the new point get inserted the same way. Because every split is by the box's own geometric center, computing which quadrant a point belongs to never needs to look at any other point in the structure — the tradeoff for that simplicity is that the split doesn't know or care whether the points are actually spread across all four quadrants evenly.
A range query prunes the same way Closest Pair of Points' strip check and the KD-tree's far-side check both do: a box's own boundary is the only thing that needs checking against the query rectangle. If the two don't overlap at all, nothing inside that box — none of its own points, none of its children's points, no matter how many levels deep — can possibly be inside the query rectangle either, so the whole subtree is skipped in one O(1) test. This is what makes the search cheap: a query rectangle covering a small corner of the plane prunes entire quadrants without ever looking at the points they contain.
function makeQuadtree(boundary, capacity = 4, maxDepth = 8, depth = 0) {
return { boundary, capacity, maxDepth, depth, points: [], divided: false };
}
function contains(node, pt) {
const b = node.boundary;
return pt[0] >= b.x && pt[0] < b.x + b.w && pt[1] >= b.y && pt[1] < b.y + b.h;
}
function subdivide(node) {
const { x, y, w, h } = node.boundary;
const hw = w / 2, hh = h / 2;
node.nw = makeQuadtree({ x, y, w: hw, h: hh }, node.capacity, node.maxDepth, node.depth + 1);
node.ne = makeQuadtree({ x: x + hw, y, w: hw, h: hh }, node.capacity, node.maxDepth, node.depth + 1);
node.sw = makeQuadtree({ x, y: y + hh, w: hw, h: hh }, node.capacity, node.maxDepth, node.depth + 1);
node.se = makeQuadtree({ x: x + hw, y: y + hh, w: hw, h: hh }, node.capacity, node.maxDepth, node.depth + 1);
node.divided = true;
const old = node.points;
node.points = [];
for (const pt of old) insertIntoChild(node, pt); // re-home every existing point
}
function insertIntoChild(node, pt) {
return insert(node.nw, pt) || insert(node.ne, pt) || insert(node.sw, pt) || insert(node.se, pt);
}
function insert(node, pt) {
if (!contains(node, pt)) return false;
if (!node.divided) {
// maxDepth guard: past this depth, stop splitting and just keep growing this
// box's own list -- see this page's Pitfalls section for what skipping it does.
if (node.points.length < node.capacity || node.depth >= node.maxDepth) {
node.points.push(pt);
return true;
}
subdivide(node);
}
return insertIntoChild(node, pt);
}
function rangeQuery(node, range, found = []) {
const b = node.boundary;
const overlaps = !(range.x > b.x + b.w || range.x + range.w < b.x ||
range.y > b.y + b.h || range.y + range.h < b.y);
if (!overlaps) return found; // whole subtree pruned, points never even read
for (const pt of node.points) {
if (pt[0] >= range.x && pt[0] < range.x + range.w &&
pt[1] >= range.y && pt[1] < range.y + range.h) {
found.push(pt);
}
}
if (node.divided) {
rangeQuery(node.nw, range, found);
rangeQuery(node.ne, range, found);
rangeQuery(node.sw, range, found);
rangeQuery(node.se, range, found);
}
return found;
}Skipping the max-depth guard doesn't crash — it silently deletes points. The
temptation is to drop it: if (node.points.length < node.capacity) alone looks like
a complete, simpler version of the same check. It isn't. Feeding 500 inserts of the exact
same coordinate to that stripped-down version, capacity 3: insert() itself
reports success only 3 times (matching capacity — every insert after that recurses into
subdivide() again and again, since splitting a box by its geometric center never
separates two points that share one exact coordinate), and the recursion keeps halving the box's
width every level until 64-bit float precision runs out — at depth 56 in this test, box width
underflows to 6.9e-15. Past that point contains() starts returning
false for every child, insertIntoChild returns false, and
subdivide's own re-homing loop — for (const pt of old) insertIntoChild(node,
pt) — never checks that return value. The point it was trying to re-home just vanishes,
mid-recursion, with no error anywhere. Counting every point actually reachable in the finished tree
after all 500 inserts: zero — not even the 3 that insert() itself
claimed succeeded, because those 3 got swept into the same losing cascade during a later
point's subdivide() call. A query afterward returns nothing, silently, and nothing in
the run ever threw. The maxDepth guard fixes this by giving every box a depth past
which it simply keeps appending to its own list instead of trying to split again — re-running the
identical 500-duplicate-coordinate test with the guard in place (depth 8): all 500 succeed and all
500 are actually stored.
The guard that fixes data loss doesn't fix the complexity. With
maxDepth in place, those same 500 duplicate points don't vanish — but they also don't
spread across four quadrants the way the capacity check assumes. They all land in the one box that
happens to contain that exact coordinate, and once that box hits depth 8 it stops trying to split
at all: the finished tree has a single leaf holding all 500 points against a
nominal capacity of 3. Nothing is wrong or lost, but any range query touching that
box now degrades to a linear scan of 500 points — the same "correct answer, no longer fast" shape
as the KD-tree's own collinear-data pitfall, just
triggered by identical points piling into one region instead of a whole axis losing variance.
Range queries themselves are correct when pruning is used. Checked against a brute-force linear scan across 5,000 random trials (1 to 60 points each, random query rectangles): zero mismatches. This is a different check from the two above — it confirms the pruning logic never throws away a real match, only that clustered input can make the tree itself lopsided.
Anywhere 2D space itself — not just a fixed set of points — needs to be addressed and queried repeatedly: broad-phase collision detection in games and physics engines (only objects whose boxes actually overlap need the expensive precise check), viewport culling in map and GIS software (don't render or query features outside the visible rectangle), and image/mesh compression schemes that recursively subdivide a region only where detail actually requires it. The fixed, coordinate-derived quadrant boundaries matter here specifically because two separate systems (a renderer and a physics engine, say) can independently compute the same region boundary for the same coordinates without sharing tree state — a KD-tree's data-dependent median split can't offer that, since the split points depend on insertion history.
Insert: O(log n) average — each split roughly quarters the point
count of a region, so a tree over evenly-spread data reaches depth O(log₄ n). Worst
case is O(maxDepth), effectively O(1) once the depth cap is hit, but at
the cost documented above: a box that hits the cap stops shrinking and can accumulate arbitrarily
many points. Range query: O(log n + k) for k results
under reasonably spread data — descend and prune down to the relevant boxes, then read off every
match; the 5,000-trial stress test above confirms correctness but the pitfalls above show the
"reasonably spread" assumption is exactly the thing clustered data breaks. Space:
O(n) points stored total, plus one node object per box actually created by a split —
bounded by 4 · min(n / capacity, 4^maxDepth) in the worst case.
This site's guide, Choosing a Spatial Structure, compares this entry against the other seven Spatial entries that share the same "index points, query later" question side by side.