Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Interval trees: prune overlap search with subtree maximums

Last updated: 5 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

An interval search tree orders intervals by start and stores the maximum end reachable in each subtree. To find any overlap with a half-open query [low, high), first check the current interval. A left subtree whose maximum end is at most low cannot overlap, so the search can skip it. The maximum field must be recomputed after insertion, deletion, or rotation. With a balanced underlying tree, one overlap search takes O(log n) in the usual augmented search bound; this teaching code uses an ordinary unbalanced BST and therefore has O(h) search and insertion for actual height h, up to O(n).

Operational case

Maintenance windows occupy [19, 26), [31, 42), [47, 61), [52, 58), and [83, 91). A request for [25, 32) intersects [19, 26), even though only one time unit overlaps; [62, 80) intersects none. Half-open endpoints make [61, 83) nonoverlapping with both [47, 61) and [83, 91). The augmented maximum can rule out an entire left subtree, but it cannot fix a chain-shaped BST. For a live calendar, pair the augmentation with balancing and define what should happen when many windows overlap.

Working Python program

python
class WindowNode:
    def __init__(self, start, end):
        self.start = start
        self.end = end
        self.max_end = end
        self.left = None
        self.right = None

def add_window(node, start, end):
    if node is None:
        return WindowNode(start, end)
    if start < node.start:
        node.left = add_window(node.left, start, end)
    else:
        node.right = add_window(node.right, start, end)
    node.max_end = max(node.end, node.left.max_end if node.left else node.end, node.right.max_end if node.right else node.end)
    return node

def first_overlap(node, low, high):
    while node:
        if node.start < high and low < node.end:
            return (node.start, node.end)
        if node.left and node.left.max_end > low:
            node = node.left
        else:
            node = node.right
    return None

root = None
for start, end in ((47, 61), (19, 26), (52, 58), (83, 91), (31, 42)):
    root = add_window(root, start, end)
print(first_overlap(root, 25, 32))
print(first_overlap(root, 62, 80))

Output

Output
(19, 26)
None

Time, space, and tradeoff

The tree stores O(n) nodes and one max-end value per node. Building by repeated insertion is O(nh) under a current height bound h; an adversarial order can give O(n²) total. A single overlap lookup follows O(h) nodes in this unbalanced implementation. Returning every overlap can cost at least O(k) for k results and may visit more branches. Reject invalid intervals with start at or beyond end, and preserve max-end values during deletion and rotation. The returned first overlap is not guaranteed to be the earliest or shortest one.

Common Mistakes

  • Do not claim logarithmic worst-case search for an unbalanced BST.
  • Do not use inclusive endpoint comparisons with this half-open contract.
  • Do not leave max-end metadata stale after a structural edit.

Connected lessons

Apply it: Project: own a maintenance index and work queue and Index and queue invariants.

K-d trees: exact nearest depot with plane pruning handles a related query contract.

Packed R-tree: search intersecting depot rectangles adds a related operation contract.

Bounding-volume hierarchies: prune box overlap searches adds another spatial query contract.

Disjoint interval unions: maintain covered maintenance time adds a related structure with a different operation boundary.

Segment-tree stabbing indexes: list intervals active at one point adds a related structure with a different operation boundary.

data structures
range-query-structures
Storage details