Introduction

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.

Try It: Watch a Query

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">Click anywhere on the canvas to drop a query point (the ring). Each box is a region carved out by the tree; press Step to watch the search open or prune boxes one decision at a time.</p>
<svg id="scene" class="scene" viewBox="0 0 480 360" xmlns="http://www.w3.org/2000/svg"></svg>
<div class="status" id="status">Click the canvas to place a query point.</div>
<div class="btns">
  <button id="step" type="button">Step</button>
  <button id="run" type="button">Run to end</button>
  <button id="reset" type="button" class="ghost">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; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Step-through nearest-neighbor search over a small k-d tree, driven by a precomputed plan of descend/bound/prune actions.
const W = 480, H = 360;
// The fixed set of 2D points the tree is built over.
const POINTS = [
  { x: 80,  y: 60  },
  { x: 300, y: 40  },
  { x: 400, y: 260 },
  { x: 140, y: 220 },
  { x: 60,  y: 320 },
  { x: 420, y: 100 },
  { x: 230, y: 150 },
];

// Build a balanced k-d tree by alternately splitting on x and y at the median.
function buildTree(pts, depth, bounds){
  if (pts.length === 0) return null;
  const axis = depth % 2; // 0 = split on x, 1 = split on y
  const sorted = [...pts].sort((a,b) => axis === 0 ? a.x - b.x : a.y - b.y);
  const mid = Math.floor(sorted.length / 2);
  const point = sorted[mid];
  const left = sorted.slice(0, mid);
  const right = sorted.slice(mid + 1);
  let leftBounds, rightBounds;
  if (axis === 0){
    leftBounds = { ...bounds, x2: point.x };
    rightBounds = { ...bounds, x1: point.x };
  } else {
    leftBounds = { ...bounds, y2: point.y };
    rightBounds = { ...bounds, y1: point.y };
  }
  return {
    point, axis, bounds, id: 'n' + (nodeSeq++),
    left: buildTree(left, depth + 1, leftBounds),
    right: buildTree(right, depth + 1, rightBounds),
  };
}
let nodeSeq = 0;
const root = buildTree(POINTS, 0, { x1: 0, y1: 0, x2: W, y2: H });

function dist2(a,b){ const dx=a.x-b.x, dy=a.y-b.y; return dx*dx+dy*dy; }

// The search plan is precomputed as a flat list of visit/bound actions so Step can replay it one move at a time.
let query = null;
let plan = [];   // flat list of {visit} and {bound} actions in recursive order
let planIdx = 0;
let best = null, bestD = Infinity;
let visitedIds = new Set();
let prunedIds = new Set();
let finished = false;

// Recursively record "visit this node" then "test whether the far side needs opening".
function buildPlan(node){
  if (!node) return;
  plan.push({ type: 'visit', node });
  const axis = node.axis;
  const diff = axis === 0 ? query.x - node.point.x : query.y - node.point.y;
  const nearChild = diff <= 0 ? node.left : node.right;
  const farChild  = diff <= 0 ? node.right : node.left;
  buildPlan(nearChild);
  plan.push({ type: 'bound', node, farChild, diff });
}

function startSearch(pt){
  query = pt; plan = []; planIdx = 0; best = null; bestD = Infinity;
  visitedIds = new Set(); prunedIds = new Set(); finished = false;
  buildPlan(root);
  document.getElementById('log').innerHTML = '';
  draw();
  setStatus('Query placed — press Step to begin the search.', '');
  document.getElementById('step').disabled = false;
  document.getElementById('run').disabled = false;
}

function logLine(text, cls){
  const l = document.getElementById('log');
  const d = document.createElement('div');
  d.className = cls || '';
  d.textContent = text;
  l.appendChild(d);
  l.scrollTop = l.scrollHeight;
}

// Execute exactly one action from the plan; expand the far subtree's own plan inline if the bound test says it must be opened.
function step(){
  if (finished || planIdx >= plan.length){
    finished = true;
    document.getElementById('step').disabled = true;
    document.getElementById('run').disabled = true;
    setStatus(i18nFmt('Done — opened %n% of %m% points.', { n: visitedIds.size, m: POINTS.length }), 'ok');
    logLine('Search finished.', 'done');
    draw();
    return;
  }
  const action = plan[planIdx++];
  if (action.type === 'visit'){
    const node = action.node;
    visitedIds.add(node.id);
    const d = dist2(query, node.point);
    if (d < bestD){ bestD = d; best = node.point; }
    logLine(i18nFmt('Visit point (%x%, %y%) — best distance so far: %d%px.', { x: node.point.x, y: node.point.y, d: Math.round(Math.sqrt(d)) }), 'visit');
  } else {
    // bound test: distance to splitting line vs current best distance
    const lineDist2 = action.diff * action.diff;
    if (action.farChild && lineDist2 < bestD){
      logLine(i18nFmt('Splitting line is %d%px away, closer than best (%best%px) — must open that branch.', { d: Math.round(Math.sqrt(lineDist2)), best: Math.round(Math.sqrt(bestD)) }), 'visit');
      // splice the far subtree's plan right here so it runs next
      const sub = [];
      (function collect(n){
        if (!n) return;
        sub.push({ type: 'visit', node: n });
        const axis = n.axis;
        const diff2 = axis === 0 ? query.x - n.point.x : query.y - n.point.y;
        const nc = diff2 <= 0 ? n.left : n.right;
        const fc = diff2 <= 0 ? n.right : n.left;
        collect(nc);
        sub.push({ type: 'bound', node: n, farChild: fc, diff: diff2 });
      })(action.farChild);
      plan.splice(planIdx, 0, ...sub);
    } else if (action.farChild){
      markPruned(action.farChild);
      logLine(i18nFmt('Splitting line is %d%px away, already farther than best (%best%px) — prune this branch.', { d: Math.round(Math.sqrt(lineDist2)), best: Math.round(Math.sqrt(bestD)) }), 'prune');
    }
  }
  draw();
}

function markPruned(node){
  if (!node) return;
  prunedIds.add(node.id);
  markPruned(node.left);
  markPruned(node.right);
}

function runToEnd(){
  let guard = 0;
  while (!finished && guard++ < 500) step();
}

function setStatus(t, cls){ const s = document.getElementById('status'); s.textContent = t; s.className = 'status ' + cls; }

// Render the tree's bounding boxes (unopened / opened / pruned) plus the points, query, and the current best-link line.
function drawBoxes(node, svg){
  if (!node) return;
  const b = node.bounds;
  const cls = prunedIds.has(node.id) ? 'pruned' : (visitedIds.has(node.id) ? 'opened' : 'unopened');
  const rect = document.createElementNS('http://www.w3.org/2000/svg','rect');
  rect.setAttribute('x', b.x1); rect.setAttribute('y', b.y1);
  rect.setAttribute('width', b.x2 - b.x1); rect.setAttribute('height', b.y2 - b.y1);
  rect.setAttribute('class', 'box ' + cls);
  svg.appendChild(rect);
  drawBoxes(node.left, svg);
  drawBoxes(node.right, svg);
}

function draw(){
  const svg = document.getElementById('scene');
  svg.innerHTML = '';
  if (root) drawBoxes(root, svg);
  for (const p of POINTS){
    const c = document.createElementNS('http://www.w3.org/2000/svg','circle');
    c.setAttribute('cx', p.x); c.setAttribute('cy', p.y); c.setAttribute('r', 5);
    const isBest = best && best.x === p.x && best.y === p.y;
    c.setAttribute('class', 'pt' + (isBest ? ' best' : ''));
    svg.appendChild(c);
  }
  if (query){
    const q = document.createElementNS('http://www.w3.org/2000/svg','circle');
    q.setAttribute('cx', query.x); q.setAttribute('cy', query.y); q.setAttribute('r', 8);
    q.setAttribute('class', 'query');
    svg.appendChild(q);
    if (best){
      const line = document.createElementNS('http://www.w3.org/2000/svg','line');
      line.setAttribute('x1', query.x); line.setAttribute('y1', query.y);
      line.setAttribute('x2', best.x); line.setAttribute('y2', best.y);
      line.setAttribute('class', 'link');
      svg.appendChild(line);
    }
  }
}

document.getElementById('scene').addEventListener('click', (ev) => {
  const svg = ev.currentTarget;
  const rect = svg.getBoundingClientRect();
  const x = (ev.clientX - rect.left) * (W / rect.width);
  const y = (ev.clientY - rect.top) * (H / rect.height);
  startSearch({ x, y });
});
document.getElementById('step').addEventListener('click', step);
document.getElementById('run').addEventListener('click', runToEnd);
document.getElementById('reset').addEventListener('click', () => {
  query = null; plan = []; planIdx = 0; best = null; bestD = Infinity;
  visitedIds = new Set(); prunedIds = new Set(); finished = false;
  document.getElementById('log').innerHTML = '';
  document.getElementById('step').disabled = true;
  document.getElementById('run').disabled = true;
  setStatus('Click the canvas to place a query point.', '');
  draw();
});
document.getElementById('step').disabled = true;
document.getElementById('run').disabled = true;
draw();
Result
Console

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 Real Complexity

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 dd found so far, check the other side with one cheap test: is the query's distance to the splitting line itself already ≥d\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 dd, 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)O(\log n) on average — most branches get pruned on the cheap distance-to-line test alone. The worst case is still O(n)O(n): an unlucky query can force the algorithm to open almost every branch.
  • The curse of dimensionality. As dimension dd grows, distances to splitting hyperplanes shrink relative to distances between points, so the bound dist(line)≥d\text{dist(line)} \geq d succeeds less and less often. Past roughly d≈20d \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.

Where It Matters

"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.

Conclusion

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)O(\log n) in the plane and can still be O(n)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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/kd-tree-nearest-neighbor/Content licensed under CC BY-NC 4.0.