Three of this site's other Spatial entries — KD-tree, Quadtree, R-tree — answer questions about points or rectangles sitting in 2D space. An interval tree answers a related but genuinely different question, in one dimension: given a pile of ranges — meeting times, IP blocks, chromosome coordinates, line numbers a function spans — which of them overlap a query range? A linear scan checking every interval works, but costs O(n) per query no matter how many times you ask. An interval tree costs O(n log n) to build once, and O(log n + k) per query after that, where k is just the number of matches actually found — the same build-once-query-often trade those three make, applied to ranges instead of points or boxes.
The mechanism is different from all three, though: no partitioning of space at all. An interval
tree is a plain binary search tree, ordered by
each interval's low endpoint exactly the way a normal BST orders by value — with one
extra piece of bookkeeping at every node: the largest high endpoint anywhere in that
node's subtree. That single augmented number is what turns an ordinary BST search into something
that can rule out entire subtrees of ranges at once.
Ten intervals, built by repeatedly picking the median (by low endpoint) of whatever's left — the same halving trick KD-tree uses, so the tree comes out balanced regardless of how the intervals happen to be spread out. Press Step or Run to watch it build, node by node, then automatically switch to a query for the range [58, 63]: watch which subtrees get skipped outright, and why, on both the tree diagram and the number line below it.
Building is the same recursive median split as KD-tree: sort whatever's left by
low, put the median interval at this node, recurse on the half before it and the half
after it. Because the split point is always the middle of the sorted order — not the middle of the
value range — each recursive call gets exactly half the remaining intervals, which keeps the tree at
O(log n) depth no matter how the actual endpoints are distributed. Once both children are built, this
node's own max is set to the largest of: its own high, its left child's
max, and its right child's max — computed bottom-up, after the recursion
returns, since it depends on both subtrees already being finished.
Two things fall out of building by low: first, this is a real BST invariant — every
interval in a node's left subtree has a low at or before this node's, and every interval
in its right subtree has a low at or after it, the same ordering guarantee binary-search-tree.html's own
inorder() relies on. Second, that ordering is what makes the max field
useful for pruning in two different, asymmetric ways during a query for range
[qlo, qhi]:
max — the single largest
high anywhere inside it — is still less than qlo. If nothing in there
reaches even that far, nothing in there can possibly overlap a query that starts at
qlo.low already exceeds qhi. Every interval in the right subtree has a
low at or after this node's (the BST invariant above), so if this node's
low is already past the query's end, every descendant's is too — none of them can
start early enough to overlap.Whatever isn't pruned gets checked directly (does [low, high] actually overlap
[qlo, qhi]? — low ≤ qhi && qlo ≤ high) and recursed into. Checked directly
on this page's own ten intervals for the demo query [58, 63]: the root G
[45,65] prunes its entire left subtree in one shot — C's subtree has
max 55, short of 58 — skipping five intervals (A, H, C, E, B) without
looking at a single one of them, then finds real overlaps at G, D,
and I while pruning J alone at the last step (F's
own low, 70, is already past 63). Four nodes visited out of ten to find all three real matches.
function buildIntervalTree(intervals) {
if (intervals.length === 0) return null;
const sorted = [...intervals].sort((a, b) => a.low - b.low);
const mid = Math.floor(sorted.length / 2);
const node = {
interval: sorted[mid],
left: buildIntervalTree(sorted.slice(0, mid)),
right: buildIntervalTree(sorted.slice(mid + 1)),
};
node.max = sorted[mid].high;
if (node.left) node.max = Math.max(node.max, node.left.max);
if (node.right) node.max = Math.max(node.max, node.right.max);
return node;
}
function overlaps(a, b) {
return a.low <= b.high && b.low <= a.high;
}
function searchOverlap(node, query, results = []) {
if (!node) return results;
// Left subtree can only hold a match if something in it reaches at least query.low.
if (node.left && node.left.max >= query.low) {
searchOverlap(node.left, query, results);
}
if (overlaps(node.interval, query)) results.push(node.interval);
// Every interval in the right subtree has a `low` >= this node's own -- if this
// node's low is already past query.high, none of them can overlap either.
if (node.interval.low <= query.high) {
searchOverlap(node.right, query, results);
}
return results;
}Forgetting to merge children into max looks fine until a query needs the
merged value. A plausible-looking mistake: set node.max = sorted[mid].high and
stop there, never folding in node.left.max/node.right.max. Every leaf still
gets a correct max (it has no children to merge), and small, shallow queries often still
land on the right answer by luck — which is exactly what makes this dangerous. Checked directly on
this page's own ten intervals: querying [93, 96] should find both
I [50,95] and J [80,100]. The buggy
version finds only J — at the root G, the search needs to descend
through F into D [60,90] to reach
I, but the buggy D reports its own unmerged
max as 90 (its own high, since it never merged in I's 95),
which is less than the query's 93 — so the entire D subtree, I
included, gets silently pruned as unreachable even though I is sitting right there
inside it. A 20,000-trial stress test against random interval sets (1-30 intervals each) found this
exact bug disagreeing with a brute-force scan in 30.2% of trials — not a rare
edge case, close to a coin flip.
One very wide interval poisons pruning for the whole tree, not just its own
subtree. Because max is merged upward through every ancestor, a single interval
spanning nearly the entire value range pushes a large max onto every node on the path
from it to the root — which means the left-subtree prune (left.max >= query.low) stops
firing for any of those ancestors, since their max is now dominated by the one wide
interval regardless of what else is actually in the subtree. Measured directly: 500 random narrow
intervals plus 2,000 random queries visited an average of 13.45 nodes per query;
adding one single interval spanning nearly the whole range to that same 500 pushed the average up to
39.76 nodes per query (both figures averaged over 20 independent trials) — roughly
3x the work, from one interval out of 501, because it happens to sit on the path to almost every
prune check in the tree.
An empty interval set has nothing to overlap.
buildIntervalTree([]) returns null, and
searchOverlap(null, query) correctly returns an empty array right back rather than
throwing — the function's first line is exactly this guard, the same shape of edge case KD-tree's own nearestNeighbor(null, target)
handles.
Calendar and meeting-room software (does this new event conflict with any existing one?),
genomic-feature lookups (which genes overlap this chromosome region — the core operation tools like
bedtools are built around), IP-range and firewall-rule matching (which rule's CIDR block
contains this address), and "which function/scope contains line N" queries in an IDE or debugger. The
common shape is the same one motivating this page: a fixed-ish set of ranges, checked against many
different query ranges over time. For the different question of picking the largest
non-overlapping subset of weighted intervals (not finding everything that overlaps one query range),
see Weighted Interval Scheduling instead
— a real interval tree doesn't help there, since that problem needs the single best compatible
predecessor, not every overlap.
Not to be confused with a segment tree: a segment tree fixes the query ranges in advance (asking "what's the min/sum over indices 3 to 7") over data that changes, where an interval tree fixes the data (the intervals) and answers arbitrary overlap queries against them. R-tree's own rectangles are the direct 2D generalization of what this page indexes along a single axis — an R-tree entry is really just two interval trees' worth of range, one per dimension, grouped into boxes instead of kept separate.
Build: like KD-tree, this reference implementation re-sorts the current subset at
every level to find the median, costing O(n log n) per level across
O(log n) levels — O(n log² n) total, traded for clarity. A production
implementation finds the median with a linear-time selection algorithm instead, bringing the real
bound down to O(n log n). A fully dynamic version that supports insertion after the
initial build needs a self-balancing BST underneath (a red-black tree, augmented with the same
max field, is the standard choice) to keep that O(log n) depth guarantee as intervals are
added one at a time — this page's demo, like KD-tree's, only covers the batch-build case.
Query: commonly stated as O(log n + k), where k is the number of
overlaps actually reported — confirmed directly in the first Pitfall's own stress test, where the
correctly-merged tree visited far fewer nodes than a full scan on average across 20,000 trials. But
that bound assumes the max-based pruning actually fires; the second Pitfall above
measures that same query degrading to visiting roughly 3x more nodes once a single sufficiently wide
interval defeats the left-subtree prune on most of the paths that would otherwise use it.
Space: O(n) — one tree node per input interval, plus one number's worth
of extra bookkeeping per node.
This site's guide, Choosing a Spatial Structure, sets this entry aside from the seven it actually compares, for the exact reason this page's own opening paragraph gives: a related but genuinely different question, over one-dimensional ranges instead of 2D points or rectangles.