Every search tree on this site so far orders nodes by a
single key: a number, a string, one comparable value. That works because a 1D key has a natural
total order — "less than" always means something. A 2D point doesn't: is (3, 9) less
than (7, 2)? Less in x, greater in y — there's no single
answer, so there's no obvious way to drop points into a plain
binary search tree and keep its ordering
guarantees. A KD-tree (k-dimensional tree) sidesteps the problem by not picking
one order at all: it alternates. The root splits the point set on x, the root's
children split on y, their children split on x again, and so on — each
level cycling through the dimensions, so no single axis ever has to carry the whole ordering by
itself.
This opens a new Spatial category — the site's Geometry algorithms (Closest Pair of Points, Delaunay Triangulation, Fortune's Algorithm, and six others) all operate on a fixed point set once; a KD-tree is what you build when the same point set needs to answer many nearest-neighbor or region queries after that, without re-scanning every point from scratch each time.
Eleven points, split alternately on x then y by median at each level.
Press Step or Run to watch the tree get built one split at a time
— each split draws a line clipped to the region it's dividing, the classic KD-tree "carved-up
plane" picture. Once the tree is built, the demo automatically switches to a nearest-neighbor query
for the square point Q: watch the search descend toward Q first, track the best
point found so far (dashed circle = current search radius), and backtrack into a sibling subtree
only when that subtree's splitting plane is still closer than the best distance found — everything
else gets skipped and fades out.
Building the tree is recursive median partitioning: sort the current point set by whichever axis this level splits on, put the median point at this node, and recurse on the points before it (one child) and after it (the other child), flipping to the next axis each time. Because the split is always at the median, each recursive call gets roughly half the points its parent had — the same halving that keeps a balanced BST at O(log n) depth, just alternating which coordinate does the halving.
Searching for the nearest neighbor of a query point starts the same way a BST search would: at each node, compare the query against that node's splitting axis and descend toward whichever side the query falls on — this reaches a small region actually containing the query point in O(log n), and every point visited along the way is a legitimate candidate for "best so far." The part that makes this more than a BST lookup is the trip back up: at each node on the way back, the *other* child — the one not descended into — might still hold something closer, because being on the wrong side of one split doesn't mean being far away in actual distance. The fix is the same "distance to a boundary, not to any specific point" argument Closest Pair of Points uses for its strip check: if the query's perpendicular distance to this node's splitting plane already exceeds the best distance found so far, then every point on the far side is provably farther than that plane, which is farther than the current best — the entire subtree can be skipped without looking at a single point in it. Only when the plane is still closer than the best-so-far does the far side get a visit.
function buildKDTree(points, depth = 0) {
if (points.length === 0) return null;
const axis = depth % 2; // 0 = x, 1 = y — alternate every level
const sorted = [...points].sort((a, b) => a[axis] - b[axis]);
const mid = Math.floor(sorted.length / 2);
return {
point: sorted[mid],
axis,
left: buildKDTree(sorted.slice(0, mid), depth + 1),
right: buildKDTree(sorted.slice(mid + 1), depth + 1),
};
}
function dist2(a, b) {
const dx = a[0] - b[0], dy = a[1] - b[1];
return dx * dx + dy * dy; // skip the sqrt — only relative order matters
}
function nearestNeighbor(root, target) {
let best = null;
let bestD2 = Infinity;
function visit(node) {
if (!node) return;
const d2 = dist2(node.point, target);
if (d2 < bestD2) { bestD2 = d2; best = node.point; }
const axis = node.axis;
const diff = target[axis] - node.point[axis];
const nearSide = diff <= 0 ? node.left : node.right;
const farSide = diff <= 0 ? node.right : node.left;
visit(nearSide); // the side the query actually falls on, always worth checking
// The far side only matters if the splitting plane itself is closer than
// the best distance found so far -- see "Why it works" above.
if (diff * diff < bestD2) {
visit(farSide);
}
}
visit(root);
return best;
}Skipping the backtrack check still terminates and still looks plausible — it's just
wrong. A version of nearestNeighbor that only ever calls
visit(nearSide) and never checks the far side at all is shorter, always finishes, and
returns a nearby point — just not reliably the nearest one. Checked directly on this
page's own 11 points: querying for the point nearest Q (this page's demo target),
the real algorithm correctly backtracks into a sibling subtree and returns K at
distance 53.85; the no-backtrack version never looks at K's subtree at all and confidently returns
C at distance 80.62 instead — 50% farther than the real answer, not a rounding
difference. This isn't a rare edge case either: a 20,000-trial stress test against random point
sets (1 to 30 points each) found the no-backtrack version disagreeing with a brute-force linear
scan in 3,193 trials — 16% of the time. The full version with the backtrack check
matched brute force in all 20,000.
A depth-balanced tree does not mean a query stays cheap. Median-by-index
splitting keeps the tree's depth balanced regardless of where the values actually fall —
even if every point shares the same y coordinate, sorting by y and
taking the middle index still produces a perfectly balanced split, because "median" here means
median position in the sorted order, not median of a spread-out range. But a split on an axis with
zero (or near-zero) variance prunes nothing: the query's perpendicular distance to that plane is
always ~0, so the "skip the far side" check in nearestNeighbor almost never fires, and
the search ends up visiting nearly everything under that node anyway. Measured directly: building
trees over both a random 2D point set and a collinear point set (all points on one line) of the
same size, both come out with identical depth at every size tested (14 levels at n=12,800) — but
the average nodes visited per nearest-neighbor query is 20.1 for the random set
versus 222.5 for the collinear one, over 200 queries each. Same tree shape,
roughly 11× more work, because the data itself — not the tree — stopped giving the pruning check
anything to work with.
An empty point set has no nearest neighbor to find. buildKDTree([])
returns null, and nearestNeighbor(null, target) correctly returns
null right back rather than throwing — visit's first line is exactly this
guard. Callers that assume the result is never null are the ones that need to handle
it, the same shape of bug Closest Pair of
Points' own Pitfalls section flags for a zero- or one-point input.
Anywhere the same point set gets queried repeatedly instead of processed once: nearest-neighbor
classification in machine learning (find the k closest labeled examples to a new
point), collision and proximity checks in games and physics engines, GIS "find the nearest gas
station" queries, and as an acceleration structure for ray tracing (which object does this ray hit
first). The common thread is amortization — building the tree costs O(n log n) once, and every
query after that is cheap, which only pays off if there are enough queries to amortize the build
over. For a single one-off "which two points are closest" question over a fixed set, Closest Pair of Points' direct divide-and-conquer
is the right tool instead — no tree to maintain.
Not to be confused with the randomized incremental trapezoidal map named as still-unbuilt future work on this site's Point in Polygon and Slab Decomposition pages: that structure answers "which region of a planar subdivision contains this point" (point-location among possibly-overlapping polygons/edges), a genuinely different question from "which of these individual points is nearest" — this page doesn't close that reference.
Build: each level halves the point count and sorts the current subset to find
the median, so — like Closest Pair of Points'
own strip re-sort — this reference implementation costs O(n log n) per level across
O(log n) levels, i.e. O(n log² n) total, traded for clarity. A production
implementation finds the median with a linear-time selection algorithm (quickselect or
nth_element) instead of a full sort, which brings the real bound down to
O(n log n).
Query: commonly stated as O(log n) on average, for data spread
reasonably across both axes — confirmed directly across the same 20,000-trial stress test above:
the real algorithm visited an average of 5.70 nodes against an average set size of 15.52, roughly
2.7× fewer than a full linear scan would need. This page's own 11-point demo visits 6 nodes to
answer its query. But average-case is not worst-case: the second Pitfall above measures the same
query degrading to visiting the large majority of nodes when the data doesn't actually vary along
one of the two axes, even though the tree's depth stays exactly as balanced as the random case's
tree. Space: O(n) — one tree node per input point.
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.