Every point-indexing structure on this site so far — KD-tree, Quadtree, R-tree,
Range Tree — builds its split from the points'
coordinates: an x threshold, a y threshold, a bounding box. That works as
long as "coordinate" means something — two independent numbers you can compare on their own. It stops
working the moment the only thing you actually have is a way to measure distance between two
things, with no coordinate axis behind it at all: the edit distance between two strings, the
great-circle distance between two points on a globe (where a naive latitude/longitude axis split
distorts badly near the poles), a similarity score between two embedding vectors whose individual
dimensions aren't independently meaningful. A Ball Tree builds its entire structure
out of nothing but pairwise distances — no axis, no threshold, no coordinate is ever inspected on its
own.
Eleven points, split recursively into nested bounding circles ("balls"). Press Step or Run to watch each ball get built: two far-apart points anchor the split, every other point joins whichever anchor it's closer to, and the resulting half gets wrapped in the smallest circle that contains it. Once the tree is built, the demo switches to a nearest-neighbor query for the square point Q — watch it descend toward the closer ball first, track the best point found so far (dashed circle = current search radius around Q), and only open a ball it already skipped past if that ball's own boundary is still closer than the best distance found. Everything else fades out, pruned without ever being opened.
Building the tree needs only a distance function. Pick any point x0, find the point
p1 farthest from it, then find the point p2 farthest from p1 —
these two anchor the split. Every point (including the anchors) joins whichever of p1/
p2 it's closer to, giving two halves. Each half's ball is just its
centroid plus the farthest distance from that centroid to any point inside — the smallest circle (in
2D; the smallest hypersphere in general) that provably contains everything in the subtree. Recurse on
each half, flipping to a fresh pair of anchors every time — no axis ever enters the picture, so the
identical code works over any distance function, in any number of dimensions, not just 2D coordinates.
Querying leans on the triangle inequality: for any point p inside a ball with center
c and radius r, dist(query, p) ≥ dist(query, c) − dist(c, p) ≥
dist(query, c) − r. That right-hand side is a lower bound on the distance from the
query to anything the ball could possibly contain — nothing has to be looked at individually to compute
it, just the ball's own center and radius. If that lower bound is already farther than the best
distance found so far, every point in the ball is provably farther too, and the whole subtree is safe
to skip. The search always visits whichever child's ball is nearer first (most likely to improve the
answer early, which tightens the bound for the sibling's prune check) and only opens the farther child
if its lower bound still beats the current best.
function dist(a, b) { return Math.hypot(a[0] - b[0], a[1] - b[1]); }
function buildBallTree(points) {
if (points.length === 0) return null;
if (points.length === 1) {
return { leaf: true, points, center: points[0], radius: 0 };
}
const cx = points.reduce((s, p) => s + p[0], 0) / points.length;
const cy = points.reduce((s, p) => s + p[1], 0) / points.length;
const center = [cx, cy];
let radius = 0;
for (const p of points) radius = Math.max(radius, dist(center, p));
// Anchor the split with the farthest-apart pair reachable from an arbitrary start —
// not the true diameter (that's expensive), but far better than two arbitrary points.
const x0 = points[0];
const p1 = points.reduce((best, p) => dist(p, x0) > dist(best, x0) ? p : best, points[0]);
const p2 = points.reduce((best, p) => dist(p, p1) > dist(best, p1) ? p : best, points[0]);
const left = [], right = [];
for (const p of points) {
(dist(p, p1) <= dist(p, p2) ? left : right).push(p);
}
if (left.length === 0 || right.length === 0) {
// every point tied exactly on both anchors -- stop subdividing, this is a leaf
return { leaf: true, points, center, radius };
}
return { leaf: false, center, radius, left: buildBallTree(left), right: buildBallTree(right) };
}
function nearestNeighbor(root, target) {
let best = null;
let bestD = Infinity;
function visit(node) {
if (!node) return;
if (node.leaf) {
for (const p of node.points) {
const d = dist(p, target);
if (d < bestD) { bestD = d; best = p; }
}
return;
}
const dLeft = dist(target, node.left.center) - node.left.radius;
const dRight = dist(target, node.right.center) - node.right.radius;
const [nearChild, farChild, dFar] = dLeft <= dRight
? [node.left, node.right, dRight]
: [node.right, node.left, dLeft];
visit(nearChild); // the closer ball first -- always worth opening
// The far ball only matters if its own lower bound is still closer
// than the best distance found so far -- see "Why it works" above.
if (dFar < bestD) {
visit(farChild);
}
}
visit(root);
return best;
}Forgetting to subtract the radius still terminates and still looks plausible — it's just
wrong. A common way to write this bug: compare dist(target, node.left.center)
directly against bestD, without subtracting node.left.radius first. It reads
almost the same, compiles, and returns a point every time — just not reliably the nearest one,
because it prunes based on distance to a ball's center instead of distance to its
boundary, which discards balls that still reach closer than the reported center distance
suggests. Stress-tested directly: 20,000 trials of random point sets (1 to 30 points each), correct
implementation against a brute-force linear scan, then the radius-less version against the same oracle.
The correct version matched brute force in all 20,000. The radius-less version disagreed in 3,662 —
18.3% of the time, not a rare edge case.
Sibling balls overlap — unlike every other Spatial entry's split. KD-tree's two sides of a splitting plane never overlap; Quadtree's four quadrants never overlap. A ball tree's two child balls can, and often do — nothing about the construction rules it out, since each ball only has to cover its own half, not stay clear of its sibling's. Measured directly: building 200 trees over 40 random points each and checking every internal node's two children, 1,440 of 4,840 sibling pairs — 29.8% — actually overlap. That's not a correctness problem (the lower-bound prune check above is still exact regardless), but it is a real, structural reason a ball tree's pruning is often looser than a KD-tree's on the same data: this page's own demo query for Q shows it directly — after the near ball is fully searched, the far ball's own lower bound (50.8) is still less than the best distance found so far (53.85), so the far side genuinely has to be opened, not just theoretically considered.
"Ball trees win in high dimensions" doesn't hold up when actually checked. That
claim gets repeated often enough to sound settled, so it was worth testing directly rather than taking
on faith: the reference implementation above generalizes to any number of dimensions with zero changes
(it never inspects an individual coordinate, only ever calls dist), so it was run against
a naive KD-tree-style splitter that cycles through axes, both built over the same 400 uniform-random
points, averaged over 10 independently-built trees and 50 queries each (500 queries total per
dimension), oracle-verified correct at every dimension used below (0 mismatches across 1,200
brute-force-checked trials spanning all six). Nodes visited per query, averaged:
| Dimensions | Ball Tree | Naive axis-cycling tree |
|---|---|---|
| 2 | 32.6 | 13.9 |
| 5 | 126.8 | 62.6 |
| 10 | 349.2 | 352.5 |
| 20 | 511.8 | 400.0 (full scan) |
| 40 | 547.1 | 400.0 (full scan) |
| 80 | 549.4 | 400.0 (full scan) |
The naive axis-cycling tree clearly beat the ball tree at every dimension tested except one — at 10 dimensions the two are within 1% of each other, a real but narrow crossover, not the outright win for ball trees the common claim would predict. Both structures degrade toward visiting nearly everything as dimensions climb (799 total nodes for 400 points; the axis-cycling tree is already visiting a full scan's worth by dimension 20), which is the real, well-established curse-of-dimensionality effect — but nothing here shows a ball tree pruning better than a coordinate split once one is available. The genuine reason to reach for a ball tree over a KD-tree isn't raw dimensionality; it's whether a coordinate system exists to split on in the first place. See "Where Ball Trees show up" below for what that reason actually looks like in practice.
Anywhere the metric isn't a set of independently-splittable coordinates. scikit-learn's own
BallTree class ships with a much wider metric list than its KDTree class for
exactly this reason: KDTree is restricted to Minkowski-family metrics (Euclidean,
Manhattan, Chebyshev, and the generalized Minkowski distance) because its splits genuinely need
per-axis comparisons to mean something, while BallTree additionally supports metrics like
Haversine (great-circle distance for latitude/longitude data), Hamming, Jaccard, and arbitrary
user-supplied distance functions — none of which have individually-meaningful axes to split on, but all
of which still satisfy the triangle inequality the pruning bound above depends on. In practice: nearest
open store or nearest weather station by real-world (not flat-map) distance, nearest similar document
by a text-similarity metric, and any k-nearest-neighbor search where "coordinate" was never a
well-defined idea to begin with.
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," a genuinely different question from "which of these individual points is nearest" — this page doesn't close that reference, same as KD-tree's own page already notes.
Build: each level computes a centroid and two farthest-point scans over the current
subset (each an O(n) pass), then partitions — the same O(n) work per level as the KD-tree's per-level
sort, across O(log n) levels on typical data, giving O(n log n) total. Unlike the KD-tree's
sort, this reference implementation's farthest-point scans are already linear, no
quickselect-equivalent needed to hit that bound.
Query: O(log n) on typical, reasonably-clustered data, degrading toward
O(n) the more sibling balls overlap — this page's own 11-point demo visits 7 of 21 nodes to
answer its query, and the high-dimensional stress test above shows the same average-case bound eroding
directly as dimensionality climbs and nearly every ball ends up overlapping every other.
Space: O(n) — one leaf per input point, one internal node per split, same
shape as every other tree on this site.
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 — including VP-Tree, which answers the identical no-coordinate-system question with a single vantage point and a guaranteed-balanced split instead of this page's two-anchor centroid.