Introduction

Suppose you have a million points scattered across a map and someone drops a pin. Which point is closest? The obvious answer is to measure the distance to all million and keep the smallest. It works, but it is brute force — every query touches every point.

The k-d tree, invented by Jon Louis Bentley in 1975, does something cleverer. It organizes the points by repeatedly slicing space along one axis at a time: split by the x-coordinate, then by the y-coordinate, then x again, alternating as you go down the tree. Each cut puts roughly half the points on each side.

Once space is carved up this way, a search can prune: if an entire region lies farther away than the best point found so far, the whole branch is skipped without ever looking inside. This is not a guess or a heuristic — the geometry guarantees nothing better hides in there.

Try It: Watch the Pruning

Below are points split into a k-d tree, with the alternating cut lines drawn in. Click anywhere to drop a query point and search for its nearest neighbor. Cells the search actually visited light up; the ones it pruned — proved too far to matter — stay dim.

<p class="hint">Points are split into a <b>k-d tree</b>: cuts alternate between vertical (x) and horizontal (y). Click anywhere to drop a query point and find its nearest neighbor. Cells the search <b>visited</b> turn blue; cells it <b>pruned</b> stay gray. A brute-force scan would touch all of them.</p>
<canvas id="cv" width="420" height="320"></canvas>
<div class="status" id="status">Click on the canvas to search.</div>
<div class="btns">
  <button id="reshuffle" type="button">New points</button>
  <button id="bruteforce" type="button" class="ghost">Compare brute force</button>
</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 .7rem; line-height: 1.45; }
canvas { border: 1px solid #cdd9e3; border-radius: 8px; background: #fbfdff; cursor: crosshair; display: block; max-width: 100%; }
.status { font-size: 1rem; font-weight: 600; margin: .6rem 0; min-height: 1.4em; color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Nearest-neighbor search on a k-d tree, with branch-and-bound pruning.
// The tree alternates the splitting axis (x at depth 0, y at depth 1, ...).
// A subtree is PRUNED when the straight-line distance from the query to the
// splitting plane already exceeds the best distance found so far — nothing closer can hide on the far side. Checking one point is O(1); the tree turns
// an O(n) scan into an O(log n) average walk in low dimensions (Bentley, 1975).
const cv = document.getElementById('cv'), ctx = cv.getContext('2d');
const W = cv.width, H = cv.height, PAD = 12;
let pts = [], root = null, lastQuery = null;

function build(points, depth, bb) {
  if (!points.length) return null;
  const axis = depth % 2;
  const key = axis === 0 ? 'x' : 'y';
  points.sort((a, b) => a[key] - b[key]);
  const mid = points.length >> 1;
  const p = points[mid];
  const leftBB = { ...bb }, rightBB = { ...bb };
  if (axis === 0) { leftBB.x1 = p.x; rightBB.x0 = p.x; }
  else { leftBB.y1 = p.y; rightBB.y0 = p.y; }
  return {
    p, axis, bb,
    left: build(points.slice(0, mid), depth + 1, leftBB),
    right: build(points.slice(mid + 1), depth + 1, rightBB)
  };
}

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

// Returns {best, visited:Set, pruned:Set}. Pruned = nodes whose subtree the bound let us skip entirely.
function nearest(node, qx, qy) {
  let best = null, bestD = Infinity;
  const visited = new Set(), pruned = new Set();
  function markPruned(n) { if (!n) return; pruned.add(n); markPruned(n.left); markPruned(n.right); }
  function rec(n) {
    if (!n) return;
    visited.add(n);
    const d = dist2(n.p, qx, qy);
    if (d < bestD) { bestD = d; best = n.p; }
    const diff = (n.axis === 0 ? qx - n.p.x : qy - n.p.y);
    const near = diff < 0 ? n.left : n.right;
    const far = diff < 0 ? n.right : n.left;
    rec(near);
    // Branch-and-bound: only descend the far side if the splitting plane is within the current best radius; otherwise the whole far subtree is pruned.
    if (diff * diff < bestD) rec(far);
    else markPruned(far);
  }
  rec(node);
  return { best, bestD, visited, pruned };
}

function toScreen(v, lo, hi, span, off) { return off + (v - lo) / (hi - lo) * span; }
const SX = x => PAD + x * (W - 2 * PAD);
const SY = y => PAD + y * (H - 2 * PAD);

function draw(res) {
  ctx.clearRect(0, 0, W, H);
  // partition lines + shaded cells
  (function walk(n, depth) {
    if (!n) return;
    if (res) {
      if (res.visited.has(n)) ctx.fillStyle = 'rgba(29,53,87,.12)';
      else if (res.pruned.has(n)) ctx.fillStyle = 'rgba(160,160,160,.10)';
      else ctx.fillStyle = 'transparent';
      const x0 = SX(n.bb.x0), y0 = SY(n.bb.y0), x1 = SX(n.bb.x1), y1 = SY(n.bb.y1);
      if (ctx.fillStyle !== 'transparent') ctx.fillRect(x0, y0, x1 - x0, y1 - y0);
    }
    ctx.strokeStyle = n.axis === 0 ? '#9bb0c4' : '#c7b29b';
    ctx.lineWidth = 1; ctx.beginPath();
    if (n.axis === 0) { ctx.moveTo(SX(n.p.x), SY(n.bb.y0)); ctx.lineTo(SX(n.p.x), SY(n.bb.y1)); }
    else { ctx.moveTo(SX(n.bb.x0), SY(n.p.y)); ctx.lineTo(SX(n.bb.x1), SY(n.p.y)); }
    ctx.stroke();
    walk(n.left, depth + 1); walk(n.right, depth + 1);
  })(root, 0);
  // points
  for (const p of pts) {
    ctx.fillStyle = (res && res.best === p) ? '#e63946' : '#1d3557';
    ctx.beginPath(); ctx.arc(SX(p.x), SY(p.y), (res && res.best === p) ? 6 : 3.2, 0, 7); ctx.fill();
  }
  // query + link to nearest
  if (lastQuery) {
    ctx.fillStyle = '#0a7d33';
    ctx.beginPath(); ctx.arc(SX(lastQuery.x), SY(lastQuery.y), 5, 0, 7); ctx.fill();
    if (res && res.best) {
      ctx.strokeStyle = '#0a7d33'; ctx.setLineDash([4, 3]); ctx.beginPath();
      ctx.moveTo(SX(lastQuery.x), SY(lastQuery.y)); ctx.lineTo(SX(res.best.x), SY(res.best.y));
      ctx.stroke(); ctx.setLineDash([]);
    }
  }
}

function shuffle() {
  pts = []; for (let i = 0; i < 18; i++) pts.push({ x: Math.random(), y: Math.random() });
  root = build(pts.slice(), 0, { x0: 0, y0: 0, x1: 1, y1: 1 });
  lastQuery = null; draw(null);
  setStatus('Click on the canvas to search.');
}
function setStatus(t) { document.getElementById('status').textContent = t; }

cv.addEventListener('click', e => {
  const r = cv.getBoundingClientRect();
  const qx = (e.clientX - r.left) / r.width;   // canvas is scaled by CSS; use ratio
  const qy = (e.clientY - r.top) / r.height;
  lastQuery = {
    x: (qx * W - PAD) / (W - 2 * PAD),
    y: (qy * H - PAD) / (H - 2 * PAD)
  };
  const res = nearest(root, lastQuery.x, lastQuery.y);
  draw(res);
  const v = res.visited.size, p = res.pruned.size;
  setStatus(fmt('Visited %v% of %length% cells; pruned %p%. (Brute force would check all %length%.)', { v: v, length: pts.length, p: p }));
  console.log('nearest:', res.best, 'visited', v, 'pruned', p);
});

document.getElementById('reshuffle').addEventListener('click', shuffle);
document.getElementById('bruteforce').addEventListener('click', () => {
  if (!lastQuery) { setStatus('Click to drop a query point first.'); return; }
  let bd = Infinity, bp = null;
  for (const p of pts) { const d = dist2(p, lastQuery.x, lastQuery.y); if (d < bd) { bd = d; bp = p; } }
  const res = nearest(root, lastQuery.x, lastQuery.y);
  const agree = (bp === res.best);
  setStatus(agree
    ? fmt('Brute force and the k-d tree agree on the nearest point — but the tree visited only %size% cells.', { size: res.visited.size })
    : 'Mismatch! (this should never happen)');
  console.log('brute force nearest:', bp, '| kd-tree nearest:', res.best, '| agree:', agree);
});

shuffle();
Result
Console

Notice how few cells the search needs to open. A brute-force scan would touch every point; the k-d tree usually examines a small fraction and skips the rest. The denser and higher-dimensional the data, though, the harder pruning becomes — a tension we unpack next. See also closest pair of points.

The Real Complexity

The k-d tree is a solved, well-understood structure — no open problem here, just sharp tradeoffs.

  • Building it takes O(nlog⁡n)O(n \log n): at each level you split the points by the median along one axis, and there are about log n levels.
  • A query on a balanced tree runs in O(log⁡n)O(\log n) on average in low dimensions — the pruning you saw in the demo means most branches are never opened.
  • The worst case is O(n)O(n). If the query sits awkwardly, the search may still have to visit every cell. Pruning can fail; it is never guaranteed to save work.
  • The curse of dimensionality. As the number of dimensions d grows, points spread out so evenly that almost no branch can be safely skipped. Past roughly d ≈ 20, a k-d tree often degrades to scanning nearly everything — no faster than brute force.

So a k-d tree does not change what nearest-neighbor search costs in the abstract; it exploits structure in low dimensions to avoid the work in practice. The same branch-and-bound idea — "rule out a whole region with one cheap test" — is the engine behind countless optimization searches.

Where It Matters

"Find what is near this point" is one of the most common questions in computing, and the k-d tree is its classic answer:

  • Machine learning: the k-nearest-neighbor classifier and many clustering steps lean on fast neighbor lookups.
  • Computer graphics: ray tracers and photon mapping use k-d trees (and cousins like BVHs) to find which surfaces a ray might hit.
  • Robotics and motion planning: planners such as RRT query "nearest existing node" thousands of times while growing a tree through space.
  • Databases and GIS: spatial indexes answer range queries — "all the cafés inside this rectangle" — by pruning the same way.
  • Simulation: N-body and particle codes use k-d trees to find nearby interacting particles instead of checking every pair.

Understand the k-d tree and you understand spatial indexing in general — the family of structures, alongside motion planning, that make "search near me" instant.

Conclusion

The k-d tree hides a simple, powerful idea: carve space one axis at a time, then refuse to look where the answer cannot be. Building the tree costs O(nlog⁡n)O(n \log n), and in the plane a query becomes a tidy O(log⁡n)O(\log n) walk that ignores most of the data — exactly the pruning you watched in the demo.

Its limit is just as instructive. In high dimensions the cuts stop helping and search collapses back toward brute force. That tension — a structure that is brilliant until the geometry turns against it — is why spatial search is still an active engineering art, and why the half-century-old k-d tree remains one of the cleanest examples of trading preprocessing for query speed.

Share this article

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

Comments

Loading comments...

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