TreesData structureaka augmented interval tree, centered interval tree

Interval Tree

A balanced BST of intervals keyed by start, augmented with the maximum end in each subtree, to find all intervals overlapping a point or range in O(log n + k).

▶ VisualizePattern: IntervalsPractice (3)
Progress

Definition

An interval tree stores a dynamic set of closed intervals [lo, hi] and answers overlap queries: "which stored intervals intersect [ql, qh]?" or "which contain point x?" The standard CLRS design is a balanced Binary Search Tree (Red-Black Tree or AVL Tree) keyed on lo, where each node additionally stores maxEnd, the largest hi in its subtree. The augmentation lets a search prune whole subtrees: if maxEnd of the left subtree is less than ql, nothing on the left can overlap.

Insert and delete are ordinary balanced-BST operations plus an O(1) recomputation of maxEnd along the update path, since rotations touch only a constant number of nodes. Finding one overlapping interval is O(log n); enumerating all k overlapping intervals is O(min(n, k log n)). A different, static construction (the centered interval tree) achieves O(log n + k) for reporting.

Related but different: a Segment Tree answers aggregate queries over positions in a fixed array, whereas an interval tree answers set-membership-style queries over a changing set of intervals.

intervalsoverlap queryaugmented BSTstabbing querysweep line

Intuition

A mental model before the formal terms.

Think of meeting bookings on a calendar, sorted by start time in a BST. To find whether a new meeting [ql, qh] clashes, walk down: if the left subtree's latest end time is before ql, no meeting there can clash, so skip it entirely. That single number per node — the latest end below it — is what turns a full scan into a logarithmic search.

How it works

  1. Node fields: lo, hi, maxEnd, left, right (plus height/color for balancing).
  2. Insert: BST insert by lo; on the way back up set maxEnd = max(hi, maxEnd(left), maxEnd(right)) and rebalance, recomputing maxEnd for rotated nodes.
  3. Search one overlap(ql, qh): start at the root. If the node overlaps (lo ≤ qh and ql ≤ hi) return it. If left exists and left.maxEnd ≥ ql go left; otherwise go right. Return null at a leaf.
  4. Report all overlaps: recurse: skip a subtree if its maxEnd < ql; skip the right subtree if the node's lo > qh (all starts to the right are larger); otherwise check the node and recurse into both children.
  5. Stabbing query for point x is overlap with [x, x].

Why it works

Going left only when left.maxEnd ≥ ql is safe: if the left subtree's largest end is before ql, no interval there can reach the query, so the answer (if any) is on the right. If we go left and find nothing, then some left interval had hi ≥ ql but all had lo > qh, and since starts on the right are even larger, no right interval overlaps either. Hence a single root-to-leaf path suffices.

The BST height is O(log n) with balancing, and maxEnd is maintainable because it depends only on a node and its two children.

Operations

OperationDescriptionCost
insert(lo, hi)Balanced BST insert by lo with maxEnd maintenance.O(log n)
delete(lo, hi)Balanced BST delete with maxEnd recomputation.O(log n)
findOverlap(ql, qh)Return one overlapping interval or null via a single descent.O(log n)
findAll(ql, qh)Report all k overlapping intervals.O(min(n, k log n))
stab(x)All intervals containing x.O(min(n, k log n))

Recognition

How to tell a problem wants this.

  • A dynamic set of intervals with repeated "does anything overlap [a, b]?" or "find everything containing point x" queries.
  • Calendar booking ("My Calendar I/II/III"), collision detection, genome interval lookups.
  • Sweep-line problems where the active set needs overlap queries rather than just predecessor/successor.
“overlapping intervals” → Intervals“binary tree” → Tree Traversal

Interactive demo

Play, step, change the input. ← → and space work too.

Showing the closely related Segment Tree visualization.

Empty tree
Array a
53714628
1/65Build a sum segment tree over 8 elements. Each node stores the sum of a range; a leaf covers one index and the root covers [0,7].
Visiting (partial overlap / recursing)Fully covered — take its sumNo overlap — prunedRecomputed after update
PseudocodeLearn Segment Tree →
1build(node, l, r): if l == r: tree[node] = a[l]
2  else: build children over [l,mid], [mid+1,r]; tree[node] = left + right
3query(node, l, r, ql, qr):
4  if qr < l or r < ql: return 0            # no overlap
5  if ql <= l and r <= qr: return tree[node] # total overlap
6  return query(left) + query(right)         # partial overlap: split
7update(node, l, r, i, v): descend to leaf i, set it, recompute sums on the way up
Variables
n8
Complexity
access O(log n)
search O(n)
insert —
delete —
Speed

Pseudocode

1findOverlap(node, ql, qh):
2  while node != null:
3    if node.lo <= qh and ql <= node.hi: return node
4    if node.left != null and node.left.maxEnd >= ql: node = node.left
5    else: node = node.right
6  return null

Implementation

1import math
2 
3 
4class IntervalTree:
5    """An AVL tree of intervals keyed by START, with every node augmented by
6    max_end = the largest end in its subtree. That augmentation is the whole
7    idea — it lets a query prune an entire subtree in O(1). Nodes live in
8    parallel lists and are addressed by index."""
9 
101 · The augmentation must be repaired bottom-up after every change
11    def __init__(self) -> None:
12        self.lo: list[int] = []
13        self.hi: list[int] = []
14        self.max_end: list[float] = []
15        self.height: list[int] = []
16        self.left: list[int] = []
17        self.right: list[int] = []
18        self.root = -1
19 
20    def _h(self, i: int) -> int:
21        return 0 if i == -1 else self.height[i]
22 
23    def _max_end_of(self, i: int) -> float:
24        return -math.inf if i == -1 else self.max_end[i]
25 
26    def _pull(self, i: int) -> None:
27        self.height[i] = 1 + max(self._h(self.left[i]), self._h(self.right[i]))
28        self.max_end[i] = max(self.hi[i], self._max_end_of(self.left[i]), self._max_end_of(self.right[i]))
29 
302 · Rotations are the standard AVL ones plus a _pull() on each moved node
31    def _rotate_right(self, y: int) -> int:
32        x = self.left[y]
33        self.left[y] = self.right[x]
34        self.right[x] = y
35        self._pull(y)
36        self._pull(x)
37        return x
38 
39    def _rotate_left(self, x: int) -> int:
40        y = self.right[x]
41        self.right[x] = self.left[y]
42        self.left[y] = x
43        self._pull(x)
44        self._pull(y)
45        return y
46 
47    def _rebalance(self, i: int) -> int:
48        self._pull(i)
49        bal = self._h(self.left[i]) - self._h(self.right[i])
50        if bal > 1:
51            if self._h(self.left[self.left[i]]) < self._h(self.right[self.left[i]]):
52                self.left[i] = self._rotate_left(self.left[i])
53            return self._rotate_right(i)
54        if bal < -1:
55            if self._h(self.right[self.right[i]]) < self._h(self.left[self.right[i]]):
56                self.right[i] = self._rotate_right(self.right[i])
57            return self._rotate_left(i)
58        return i
59 
603 · Insert by start, then rebalance on the way back up
61    def _insert_at(self, i: int, lo: int, hi: int) -> int:
62        if i == -1:
63            self.lo.append(lo)
64            self.hi.append(hi)
65            self.max_end.append(hi)
66            self.height.append(1)
67            self.left.append(-1)
68            self.right.append(-1)
69            return len(self.lo) - 1
70        if lo < self.lo[i]:
71            self.left[i] = self._insert_at(self.left[i], lo, hi)
72        else:
73            self.right[i] = self._insert_at(self.right[i], lo, hi)
74        return self._rebalance(i)
75 
76    def insert(self, lo: int, hi: int) -> None:
77        self.root = self._insert_at(self.root, lo, hi)
78 
794 · The pruning rule: if the left subtree's max_end is below the query
80    # start, nothing in it can overlap, so skip it entirely
81    def _collect(self, i: int, lo: int, hi: int, out: list[tuple[int, int]]) -> None:
82        if i == -1 or self.max_end[i] < lo:
83            return  # whole subtree ends too early
84        self._collect(self.left[i], lo, hi, out)
85        if self.lo[i] <= hi and lo <= self.hi[i]:
86            out.append((self.lo[i], self.hi[i]))
87        # every start in the right subtree is >= this node's start
88        if self.lo[i] <= hi:
89            self._collect(self.right[i], lo, hi, out)
90 
91    def overlapping(self, lo: int, hi: int) -> list[tuple[int, int]]:
92        out: list[tuple[int, int]] = []
93        self._collect(self.root, lo, hi, out)
94        return out
95 
965 · A point query is the degenerate range query [p, p]
97    def stabbing(self, p: int) -> list[tuple[int, int]]:
98        return self.overlapping(p, p)
Walkthrough
  1. This version uses six parallel lists rather than a node class, which avoids one Python object per node — the same trade as the Aho-Corasick and suffix-tree entries.
  2. -math.inf is the max_end of an absent child, so max() needs no special case.
  3. _pull recomputes height and max_end together, and every structural operation ends with one.
  4. The nested indexing self.left[self.left[i]] in _rebalance reads the grandchild — dense, but it is exactly the AVL double-rotation test.
  5. max_end is typed list[float] because -math.inf is a float; using a large negative integer would keep it list[int].
Complexity (this implementation)
time O(log n) insert, O(log n + k) to report k overlapping intervals · space O(n)

Recursion depth is the tree height, about 1.44 log n, so RecursionError is unreachable for any tree that fits in memory.

Language notes
  • max(a, b, c) takes any number of positional arguments, so the three-way maximum is one call.
  • Parallel lists beat a per-node class in CPython for a structure with many small nodes; @dataclass(slots=True) is the readable middle ground.
  • sortedcontainers.SortedList plus a bisect over starts handles many interval workloads without a custom tree.
  • intervaltree on PyPI is the established library and supports deletion, merging and chopping.
Common mistakes in this language
  • Using 0 as the absent-child max_end, which breaks for negative interval ends.
  • Forgetting _pull after a rotation, leaving a stale augmentation.
  • Reading self.left[i] when i is -1, which silently reads the *last* element rather than raising — Python negative indexing makes this failure mode quieter than in C++ or JS.
Language differences that matter here
  • Python negative indexing makes the -1 absent-child sentinel actively dangerous: self.left[-1] reads the last element instead of failing, where C++ would be undefined behaviour and JS/TS would yield undefined. Every access must be guarded, and the failure is quietest in Python.
  • Three-way maximum: C++ needs std::max({a, b, c}) with an initialiser list, while JS/TS Math.max and Python max are variadic already.
  • Absent-child sentinels: -Infinity and -math.inf are natural in JS/TS and Python; C++ uses INT_MIN, which is fine only because it is never added to.
  • Node storage: C++ and JS/TS use records in a vector/array, Python uses parallel lists to avoid per-object overhead — three spellings of the same index-based design, all chosen to avoid pointer or reference invalidation.

Complexity

OperationAverageWorstNote
Access——
SearchO(log n)O(log n)One overlapping interval.
InsertO(log n)O(log n)
DeleteO(log n)O(log n)
UpdateO(log n)O(log n)Delete + insert.
Overlap query (one)O(log n)O(log n)
Overlap query (all k)O(k log n)O(n)
Stabbing queryO(k log n)O(n)
SpaceO(n)Bounds assume a balanced underlying BST (AVL or red-black).

Advantages & disadvantages

Advantages
  • Dynamic: intervals can be added and removed between queries.
  • Pruning by maxEnd gives logarithmic single-overlap search on a balanced tree.
  • Small augmentation over a standard balanced BST.
Disadvantages
  • Reporting all overlaps is not output-sensitive in the worst case for the augmented-BST version.
  • Requires a balancing scheme underneath to guarantee bounds; an unbalanced version degrades to O(n).
  • For static interval sets, sorting + Binary Search or a Segment Tree over compressed coordinates is usually simpler.

Use cases

  • Calendar and resource booking with conflict detection.
  • Collision detection along one axis in physics and rendering engines.
  • Genomics: find all genes overlapping a region.
  • Network packet classification and IP range lookups.
Use it when
  • Dynamic interval sets with overlap/containment queries (booking systems, collision checks).
  • Sweep-line algorithms whose active set must answer "does anything overlap this?"
  • Any time you would otherwise scan all intervals per query and n·q is too large.
Avoid it when
  • Intervals are static — sort them and binary search, or build a Segment Tree over compressed endpoints.
  • You only need "is the point covered?" counts — a Difference Array or sweep is simpler.
  • Queries are aggregate (sum/min over a range of an array) — that is a Segment Tree problem.

Alternatives

Segment TreeAVL TreeRed-Black TreeMerge IntervalsDifference Array

Common mistakes

  • Forgetting to recompute maxEnd after rotations or on the way up after insert/delete.
  • Using strict inequalities for overlap when intervals are closed ([1,3] and [3,5] do overlap).
  • Going right when left.maxEnd >= ql fails but also not checking whether the right subtree exists.
  • Confusing an interval tree with a segment tree and trying to answer overlap queries with the latter.

Interview patterns

  • My Calendar I: reject a booking if findOverlap returns non-null, then insert.
  • Meeting rooms II via sweep line — compare with the interval-tree approach.
  • Design a range module (add/remove/query ranges) with an ordered map of disjoint intervals.
  • Explain the maxEnd pruning argument.
Interview questions on this
Mock interviews

Interview problems

Interval List IntersectionsmediumMeeting Rooms IImediumNon-overlapping Intervalsmedium