k-d Tree Nearest Neighbor

Imagine you have already organized a million points into a k-d tree — space sliced along alternating axes, half the points on each side of every cut. Now someone drops a query point and asks: which of the million is closest?

You could walk down to the leaf that contains the query and grab whatever is there, but that leaf might hold the wrong answer entirely — the true nearest point could sit just across a dividing line, in a sibling branch you never opened. So the search cannot simply go down; it has to be willing to come back up and check other branches too.

The nearest-neighbor algorithm solves this with a single recurring question at every fork: could anything on the unexplored side possibly be closer than the best point found so far? If the honest answer is no, the whole branch — thousands of points, maybe — is thrown away without a single one of them being touched.

Below is a k-d tree built over a handful of points, drawn as nested boxes cut by alternating vertical and horizontal lines. Click anywhere to drop a query point (the ring).

<p class="hint">{{hint_para}}</p>
<svg id="scene" class="scene" viewBox="0 0 480 360" xmlns="http://www.w3.org/2000/svg"></svg>
<div class="status" id="status">{{place_hint}}</div>
<div class="btns">
  <button id="step" type="button">{{btn_step}}</button>
  <button id="run" type="button">{{btn_run}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div class="log" id="log"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
.scene { width: 100%; max-width: 480px; height: auto; background: #f7f9fb; border: 1px solid #cdd9e3;
         border-radius: 8px; cursor: crosshair; display: block; }
.status { font-size: 1rem; font-weight: 600; margin: .55rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .5rem; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }
.log { font: 12px ui-monospace, monospace; background: #10182a; color: #d7e3f0; border-radius: 8px;
       padding: .55rem .7rem; max-height: 130px; overflow-y: auto; line-height: 1.5; }
.log div.prune { color: #ff9b9b; }
.log div.visit { color: #9be6b0; }
.log div.done { color: #ffd479; font-weight: 700; }
.box { fill: none; stroke-width: 1.4; }
.box.unopened { stroke: #cdd9e3; }
.box.opened { stroke: #1d3557; stroke-width: 2; fill: rgba(29,53,87,.06); }
.box.pruned { stroke: #c92f3c; stroke-dasharray: 4 3; fill: rgba(201,41,60,.06); }
.pt { fill: #1d3557; stroke: #fff; stroke-width: 1; }
.pt.best { fill: #0a7d33; r: 7; }
.query { fill: none; stroke: #e63946; stroke-width: 2.4; }
.link { stroke: #0a7d33; stroke-width: 1.4; stroke-dasharray: 3 2; }

// Code not found

Press Step to advance the search one move at a time, or Run to end to finish it. Boxes the algorithm actually opens light up in blue; boxes it prunes — proves cannot contain anything closer — turn red and are never opened. Watch the log: every prune is justified by comparing the query's distance to the current best point against its distance to the splitting line alone.

The nearest-neighbor search over a k-d tree is fully solved — it is a clean instance of branch and bound, not an open problem. The interesting part is exactly when the pruning test succeeds.

• The descent. At each node, compare the query's coordinate (on that node's split axis) to the split value, and recurse into the matching side first — the side most likely to contain the true answer.
• The bound. After that recursive call returns with some best distance $d$ found so far, check the other side with one cheap test: is the query's distance to the splitting line itself already $\geq d$? If so, every point behind that line is at least that far away too, and the whole subtree is skipped — no need to look at any point inside it.
• The backtrack. If the splitting line is closer than $d$, the algorithm must recurse into the other side after all, because something closer could be hiding there.
• Cost. In low dimensions with well-balanced data, this keeps the number of nodes visited to about $O(\log n)$ on average — most branches get pruned on the cheap distance-to-line test alone. The worst case is still $O(n)$: an unlucky query can force the algorithm to open almost every branch.
• The curse of dimensionality. As dimension $d$ grows, distances to splitting hyperplanes shrink relative to distances between points, so the bound $\text{dist(line)} \geq d$ succeeds less and less often. Past roughly $d \approx 20$, pruning collapses and the "tree search" degenerates into checking almost everything — no better than brute force.

The tree from k-d trees is the map; this branch-and-bound test is the compass that decides, at every fork, whether a whole region can be safely ignored.

"Find the closest thing to this point, without checking everything" is a need that shows up everywhere, and the branch-and-bound search is the classic way to answer it:

• Machine learning: the k-nearest-neighbor classifier needs exactly this query, often millions of times, to label new data by its closest training examples.
• Computer graphics: ray tracers ask "which surface does this ray hit first?" — a nearest-neighbor-flavored query answered by pruning the same way.
• Robotics: motion planners like RRT repeatedly ask "what is the closest node already in my tree?" while growing a path through space.
• Geographic and recommendation systems: "nearest store," "most similar user" and "closest embedding vector" queries all reduce to the same descend-bound-backtrack pattern, sometimes traded for approximate answers when dimensions get too high to prune well.

Understand this one search and you understand the engine behind countless real-time systems that need an answer "near me" without ever scanning the whole dataset — the same branch-and-bound spirit that drives search over state spaces more generally.

The nearest-neighbor search over a k-d tree hides a small, sharp idea: at every fork, ask whether the dividing line alone is already farther than your best answer — and if it is, walk away from that entire branch without a shred of guilt. Descend toward the likely side first, bound with one distance check, backtrack only when the bound fails.

That single test is why the search is usually $O(\log n)$ in the plane and can still be $O(n)$ on a bad day, and why it quietly falls apart once dimensions climb into the dozens. It is a small piece of machinery, but it is the same branch-and-bound heartbeat that shows up anywhere a search needs to prove "there is nothing better over there" before it dares to skip looking.