The site's other four Spatial entries — KD-tree, Quadtree,
R-tree, Interval Tree — all split the data itself: KD-tree
alternates axis, Quadtree carves fixed quadrants, R-tree groups bottom-up into bounding boxes,
Interval Tree orders by one endpoint. A range tree answers the same "which points
fall inside this rectangle" question KD-tree and Quadtree answer, but reaches for a different trade
entirely: split on x only, exactly like Interval Tree splits on one endpoint, then bolt a
second, independent structure onto every node to handle y. That second structure is what
buys a guarantee neither KD-tree nor Quadtree can make: O(log² n + k) query time in
the worst case, no matter how the points are distributed — where both of those pages' own Pitfalls
sections measure real, specific inputs that push their query cost well past their average-case
bound.
The cost of that guarantee is space: a range tree spends O(n log n) instead of
O(n), because — as this page measures directly below — the average point ends up copied
into roughly log n different nodes' worth of bookkeeping, not just one.
Nine points, split by median x at every level — the same halving trick KD-tree and Interval Tree both use, but always on x,
never alternating. Press Step or Run to watch it build, each split
drawing a vertical line, then automatically switch to a range query for the dashed rectangle: watch
which vertical strips get selected whole (canonical subtrees, outlined) versus checked
point-by-point along the search path, and which points inside a selected strip still fail the
y half of the check.
Building is a plain recursive median split on x: sort whatever
points remain by x, put the median at this node, recurse on the half before it and the
half after it — never touching y at all in the primary structure. That alone would just
be a 1D search tree over x, no better than scanning for a 2D query. The second piece is
what makes it work: every node also stores its entire subtree's points, sorted by
y. A leaf's sorted list is just itself; an internal node's is its own point
merged with both children's already-sorted lists.
A query for rectangle [xlo,xhi] × [ylo,yhi] starts by walking down from the root to
find the split node: the deepest node whose x still falls inside
[xlo,xhi], where the search paths toward xlo and xhi would
diverge. From there, two separate walks fan out — one down the left spine toward xlo, one
down the right spine toward xhi. At each step of the left walk, if the current node's
x is at or past xlo, its entire right subtree has an x
range that's already guaranteed inside [xlo,xhi] — every point in it qualifies on
x without checking a single one individually. That whole subtree is added
whole, as one canonical subtree, and its own pre-sorted
y-array gets a single binary search for [ylo,yhi] to pull out exactly the
points that also pass the y half. The right walk toward xhi works the
mirror image, canonicalizing left subtrees instead. Each path node's own point still needs an
individual two-coordinate check, since it isn't covered by any canonical subtree along the way. The
walks touch only O(log n) path nodes and produce only O(log n) canonical
subtrees — regardless of how the points are actually distributed, since the median split guarantees
O(log n) depth the same way it does for Interval Tree — each costing a further
O(log n) binary search on its y-array, for O(log² n) total
before counting the k actual matches reported.
function build(points) {
if (points.length === 0) return null;
const sorted = [...points].sort((a, b) => a.x - b.x);
const mid = Math.floor(sorted.length / 2);
const node = {
point: sorted[mid],
left: build(sorted.slice(0, mid)),
right: build(sorted.slice(mid + 1)),
};
// Every node's ys is its WHOLE subtree, sorted by y -- not just its own point.
node.ys = [...sorted].sort((a, b) => a.y - b.y);
return node;
}
function ysInRange(ys, ylo, yhi) {
// Binary search for the [ylo, yhi] slice of an array already sorted by y.
return ys.filter(p => p.y >= ylo && p.y <= yhi); // production code binary-searches both ends
}
function findSplitNode(node, xlo, xhi) {
if (!node) return null;
if (node.point.x < xlo) return findSplitNode(node.right, xlo, xhi);
if (node.point.x > xhi) return findSplitNode(node.left, xlo, xhi);
return node;
}
function rangeQuery(root, xlo, xhi, ylo, yhi) {
const results = [];
const inRange = (p) => p.x >= xlo && p.x <= xhi && p.y >= ylo && p.y <= yhi;
const split = findSplitNode(root, xlo, xhi);
if (!split) return results;
if (inRange(split.point)) results.push(split.point);
let node = split.left;
while (node) {
if (node.point.x >= xlo) {
if (node.right) results.push(...ysInRange(node.right.ys, ylo, yhi)); // canonical
if (inRange(node.point)) results.push(node.point); // path node's own point
node = node.left;
} else {
node = node.right;
}
}
node = split.right;
while (node) {
if (node.point.x <= xhi) {
if (node.left) results.push(...ysInRange(node.left.ys, ylo, yhi)); // canonical
if (inRange(node.point)) results.push(node.point); // path node's own point
node = node.right;
} else {
node = node.left;
}
}
return results;
}Forgetting a path node's own point looks fine on most queries — until the point itself
would have been the only match. A plausible-looking simplification: keep the two canonical
subtree checks (node.right/node.left above) but drop the "path node's own
point" line from both walks, on the reasoning that the canonical subtrees already cover "everything
qualifying on x." They don't — the nodes actually walked over are deliberately excluded from every
canonical subtree along the way (that's what makes them a spine rather than part of one), so their own
points are the one thing nothing else checks. A 20,000-trial stress test against random point sets
(1-30 points each, random query rectangles) found this exact omission disagreeing with a brute-force
scan in 38.5% of trials — worse than a coin flip, because almost every non-trivial
query touches at least one spine node whose own point happens to qualify.
The canonical-subtree guarantee holds regardless of point distribution — measured directly
against the same adversarial case that hurt KD-tree. KD-tree's own Pitfalls section measures a depth-balanced tree
over collinear points visiting 11× more nodes per query than a random point set of
the same size, because collinear data defeats its distance-based pruning. Building a range tree over
5,000 collinear points and running 500 random-rectangle queries against it found 9.28
canonical subtrees visited on average — against log₂(5000) ≈ 12.29, and effectively
identical to the 9.29 measured over 5,000 uniformly random points with the same query
count. The median-x split that builds this tree doesn't care where the values actually sit, only their
sorted order — the same property that keeps Interval Tree's build balanced regardless of endpoint
distribution.
That guarantee is bought with real, measured space — not free. Because every point
gets copied into the ys array of every ancestor on its path to the root, total storage
across all nodes grows as O(n log n), not O(n). Measured directly: at
n=100 total ys-array entries run 5.80× the point count; at n=1,000, 8.99×; at n=10,000,
12.36×; at n=100,000, 15.69× — tracking log₂ n almost exactly (12.29, 16.61 at those last
two sizes) rather than staying flat the way KD-tree,
Quadtree, and R-tree all do at one tree node per point.
An empty point set has nothing to find. build([]) returns
null, and both findSplitNode(null, ...) and the two while (node)
loops handle a null root or a null split with no special case needed — the
same defensive shape as every other tree page's guard on this site.
The classic textbook use is exactly this page's demo: static 2D (or higher-dimensional, via nesting
one more associate structure per extra dimension) orthogonal range reporting — "every record with
price between $10-50 and rating between 4-5 stars," "every star in this patch of sky within this
brightness band." Range trees generalize past 2D by nesting: a d-dimensional range tree is
a range tree over dimension 1 whose nodes each hold a (d-1)-dimensional range tree over
the remaining dimensions, at the cost of an extra O(log n) factor in both query time and
space per added dimension. Production implementations also layer on a technique called fractional
cascading, sharing a single binary search across all canonical subtrees at one query instead of
repeating it for each — bringing the query down to O(log n + k), at the cost of
considerably more bookkeeping than this page's from-scratch build shows.
Against the site's other three point/box structures: KD-tree and Quadtree both cost less space (O(n)) and are
simpler to build, and do fine on typical data — reach for a range tree specifically when the
worst case matters, not just the average, since both of those structures' own Pitfalls
sections show real inputs that push them well past their average-case bound. R-tree solves a different problem outright (indexing existing
rectangles rather than points, built bottom-up for disk-friendly access) rather than trading the same
space-versus-guarantee axis.
Build: this reference implementation re-sorts by both x and
y at every level, costing O(n log n) per level across O(log n)
levels — O(n log² n) total, traded for clarity the same way KD-tree's and Interval Tree's reference builds do. A production
build sorts by y once up front and merges two already-sorted child lists at each node
instead of re-sorting, bringing the real bound down to O(n log n).
Query: O(log² n + k) — O(log n) canonical subtrees
found by walking the two spines, each costing a further O(log n) binary search on its
y-array, plus k for the matches actually reported. Confirmed to hold
regardless of point distribution in the second Pitfall above, unlike the two structures this one
competes most directly with. Space: O(n log n) — measured directly in
the third Pitfall above, since every point is duplicated into every ancestor's y-sorted
array on its path to the root.
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 side by side.