KD-Tree

A binary space partition of $k$-dimensional points: at each level, split by the median along one axis (cycling through the axes, or choosing the widest spread).

Construction — $O(n\log n)$

struct Node { Point p; int l = -1, r = -1; int x1, y1, x2, y2; };  // bounding box
vector<Node> t;
 
int build(int lo, int hi, int depth) {           // pts[lo, hi)
    if (lo >= hi) return -1;
    int mid = (lo + hi) / 2;
    nth_element(pts.begin() + lo, pts.begin() + mid, pts.begin() + hi,
        [&](const Point& a, const Point& b) { return depth % 2 ? a.y < b.y : a.x < b.x; });
    int cur = t.size(); t.push_back({pts[mid]});
    t[cur].l = build(lo, mid, depth + 1);
    t[cur].r = build(mid + 1, hi, depth + 1);
    pullBoundingBox(cur);
    return cur;
}

nth_element is $O(n)$ per level, so the build is $O(n\log n)$ — better than sorting at every level.

Queries

Nearest neighbour

Descend into the child containing the query point first, then check whether the other side’s bounding box could contain anything closer than the current best. If not, prune.

void nearest(int node, Point q) {
    if (node == -1 || boxDist(node, q) >= best) return;      // PRUNE
    best = min(best, dist(t[node].p, q));
    int first = ..., second = ...;                           // nearer child first
    nearest(first, q);
    nearest(second, q);
}

Expected $O(\log n)$ for random points in low dimensions; $O(n)$ worst case.

Range (rectangle) query

Fully-contained subtrees are answered from a precomputed aggregate; disjoint subtrees are pruned; partially overlapping ones are recursed into.

$O(n^{1-1/d}+\text{output})\text{— so }O(\sqrt{n})\text{ in 2D.}$

Complexity summary

Operation	2D	General $d$
Build	$O(n\log n)$	$O(dn\log n)$
Rectangle query	$O(\sqrt{n}+\text{out})$	$O(n^{1-1/d}+\text{out})$
Nearest neighbour	$O(\log n)$ expected	degrades badly with $d$
Insert (unbalanced)	$O(\log n)$
Memory	$O(n)$	$O(n)$

The curse of dimensionality

Beyond $d\approx 10$-$20$, KD-tree nearest-neighbour search degenerates to a linear scan, because the pruning bound almost never fires. For high dimensions use locality-sensitive hashing or approximate methods (HNSW), or accept the linear scan.

KD-tree vs the alternatives

Structure	Rectangle query	NN	Updates	Notes
KD-tree	$O(\sqrt{n})$	✔	✔ (rebuild periodically)	$O(n)$ memory, general $d$
2D BIT	$O({\log }^{2}n)$	✘	✔	needs a small dense grid
Persistent segment tree	$O(\log n)$	✘	✘	offline-built, online query
Offline BIT sweep	$O(\log n)$ am.	✘	✔	usually the best if offline
Range tree	$O({\log }^{2}n)$	✘	✘	$O(n\log n)$ memory
Quadtree / R-tree	varies	✔	✔	better for spatial data with extent

In competitive programming, an offline sweep with a BIT beats a KD-tree whenever the queries can be sorted. The KD-tree earns its place when queries are online and geometric (nearest neighbour, or non-rectangular regions).

Keeping it balanced under insertion

A plain KD-tree degrades as points are inserted. Two standard fixes:

• Periodic rebuild — rebuild the whole tree every $\sqrt{n}$ insertions, or rebuild any subtree that becomes too unbalanced (the scapegoat approach).
• Logarithmic method — keep $O(\log n)$ static KD-trees of sizes $1,2,4,\dots$ and merge on overflow. $O({\log }^{2}n)$ amortized insertion, $O(\log n)$ trees to query.

Uses

• Nearest neighbour / $k$ nearest neighbours
• “Points inside a rectangle”, “points inside a circle”
• Collision detection and ray tracing (though a BVH is usually better for those)
• $k$-NN classification in machine learning
• Closest pair — though divide and conquer is cleaner

See also: Other Geometric Structures · Closest Pair · 2D Queries