Interval Tree, in depth: the max-end augmented BST, tested code, query pruning and when to use something else

The structure in one picture

The model: order by start, augment with the maximum end

Use half-open intervals, [lo, hi), throughout. A meeting from 10:00 to 11:00 and one from 11:00 to 12:00 then do not overlap, adjacent ranges tile without gaps or double counting, and the length is simply hi - lo. Two half-open intervals [a, b) and [c, d) overlap exactly when a < d and c < b. Every line of code below uses that test; mixing it with closed-interval logic anywhere is the most common interval-tree bug there is.

Now take a balanced binary search tree ordered by lo, breaking ties by hi. On its own it can find intervals that start in a range, but not intervals that started long ago and are still running. The fix is one augmented field: each node stores max_hi, the largest hi anywhere in its subtree. That single number answers the crucial pruning question. If a subtree's max_hi is at most the query's lo, every interval in it ended before the query began, so the whole subtree can be skipped.

The ordering gives the second pruning rule. If a node's lo is at least the query's hi, that node and everything in its right subtree start too late to overlap. Together the two rules cut the search down to the parts of the tree that can contain answers.

The augmentation is cheap to maintain because it is local: a node's max_hi depends only on its own hi and its children's values. Any balanced tree whose rotations recompute that value for the two nodes they touch keeps it correct, in O(1) extra work per rotation. That is why the same idea runs on red-black trees, AVL trees, treaps and skip lists alike.

Implementation on a treap

The implementation below uses a treap, a binary search tree that is also a heap on random priorities, because its rotations are the simplest to augment. If rotations are unfamiliar, the BST operations article walks through them.

import random

class Node:
    __slots__ = ("lo", "hi", "prio", "max_hi", "left", "right")
    def __init__(self, lo, hi):
        self.lo, self.hi = lo, hi
        self.prio = random.random()
        self.max_hi = hi
        self.left = self.right = None

def _pull(n):                          # recompute the augmentation
    m = n.hi
    if n.left and n.left.max_hi > m:
        m = n.left.max_hi
    if n.right and n.right.max_hi > m:
        m = n.right.max_hi
    n.max_hi = m

def _rot_right(n):
    l = n.left
    n.left, l.right = l.right, n
    _pull(n); _pull(l)                 # child first, then new parent
    return l

def _rot_left(n):
    r = n.right
    n.right, r.left = r.left, n
    _pull(n); _pull(r)
    return r

def insert(n, lo, hi):
    if n is None:
        return Node(lo, hi)
    if (lo, hi) < (n.lo, n.hi):
        n.left = insert(n.left, lo, hi)
        if n.left.prio > n.prio:
            n = _rot_right(n)
    else:
        n.right = insert(n.right, lo, hi)
        if n.right.prio > n.prio:
            n = _rot_left(n)
    _pull(n)
    return n

def delete(n, lo, hi):
    if n is None:
        return None
    if (lo, hi) == (n.lo, n.hi):
        if n.left is None:
            return n.right
        if n.right is None:
            return n.left
        if n.left.prio > n.right.prio:   # rotate the doomed node downwards
            n = _rot_right(n)
            n.right = delete(n.right, lo, hi)
        else:
            n = _rot_left(n)
            n.left = delete(n.left, lo, hi)
    elif (lo, hi) < (n.lo, n.hi):
        n.left = delete(n.left, lo, hi)
    else:
        n.right = delete(n.right, lo, hi)
    _pull(n)
    return n

def overlaps(n, qlo, qhi, out):
    """Append every stored [lo, hi) that overlaps [qlo, qhi)."""
    if n is None or n.max_hi <= qlo:   # everything here ended too early
        return
    overlaps(n.left, qlo, qhi, out)
    if n.lo < qhi:                     # else n and its right subtree start too late
        if qlo < n.hi:
            out.append((n.lo, n.hi))
        overlaps(n.right, qlo, qhi, out)

Usage is root = insert(root, 10, 30) and out = []; overlaps(root, 18, 22, out). A point stabbing query for an integer x is overlaps(root, x, x + 1, out). Duplicates are allowed, and delete removes one copy. This code was checked against a brute-force scan over 60,000 random insert, delete and query operations, with max_hi verified at every node after each step; do the same with your own implementation, because an augmentation bug produces silently missing results rather than a crash.

Worked example: is the room free

Store six bookings for one room, in minutes past the hour: [5, 20), [10, 30), [12, 15), [15, 17), [17, 19) and [30, 40). The diagram above shows one valid shape of the tree; the treap's random priorities decide the actual shape, but the in-order sequence by start is always 5, 10, 12, 15, 17, 30. Now ask which bookings overlap a request for [18, 22).

1. At the root [15, 17), max_hi is 40, which exceeds 18, so the subtree may contain answers. Recurse left first.
2. At [10, 30), max_hi 30 exceeds 18. Recurse left into [5, 20): its max_hi is 20, its start 5 is below 22 and its end 20 is above 18, so report it.
3. Back at [10, 30): start 10 is below 22 and end 30 is above 18, so report it. Its right child [12, 15) has max_hi 15, at most 18, so skip that subtree without examining it.
4. Back at the root: start 15 is below 22 but end 17 is not above 18, so the root itself does not overlap. Its start is below 22, so the right subtree may still hold answers.
5. At [30, 40), max_hi 40 exceeds 18. Recurse left into [17, 19): start 17 is below 22 and end 19 is above 18, so report it.
6. Back at [30, 40): start 30 is not below 22, so neither it nor its right subtree can overlap. Stop.

The answer is [5, 20), [10, 30) and [17, 19), so the room is not free. For booking you usually want only a yes or no, so stop at the first hit: an existence query visits one root-to-leaf path plus at most one side branch, O(log n) on a balanced tree.

Complexity and the centred interval tree

Insert and delete are O(log n) expected on a treap (worst case on a red-black or AVL tree), because the augmentation adds constant work per touched node. Finding whether any interval overlaps a query is O(log n). Reporting all k overlapping intervals with the augmented tree is bounded by O(min(n, k log n)), the bound given in Cormen, Leiserson, Rivest and Stein, since each reported interval can cost a search path. In practice the visited set is usually much closer to log n + k, but do not promise that bound for this structure.

If you need O(log n + k) reporting guaranteed and the set does not change, use the centred interval tree. Choose a centre point, typically the median endpoint; intervals entirely left of it go to a left subtree, intervals entirely right go to a right subtree, and intervals that contain the centre stay at the node in two lists, one sorted by start and one sorted by end. A stabbing query for point x compares x with the centre and scans just one list from one end, stopping at the first interval that misses, then descends to one child. That gives O(log n + k) per point query and O(n log n) construction. The price is that it is static: inserting means rebuilding, and general interval-overlap queries need extra machinery on top of the stabbing query.

Alternatives and how to choose

A segment tree stores each interval in O(log n) canonical nodes over a fixed coordinate range and is the natural fit when you also need range aggregates, such as maximum concurrent bookings per hour. A k-d tree treats each interval as the point (lo, hi), which turns an overlap query into an orthogonal range query: lo below the query's hi and hi above the query's lo. And when you only need counts, such as how many intervals contain x, two Fenwick trees over sorted starts and ends answer it with prefix sums and no tree of intervals at all.

Operational guidance

Let the database do it when the data lives there. PostgreSQL has range types such as tstzrange and int4range, an overlap operator &&, and GiST indexes that accelerate it. For bookings, an exclusion constraint makes the database itself reject overlaps atomically, which an application-side check cannot do safely under concurrency:

CREATE EXTENSION IF NOT EXISTS btree_gist;     -- lets GiST handle the plain equality on room_id

CREATE TABLE booking (
    room_id  int       NOT NULL,
    during   tstzrange NOT NULL,                -- half-open [start, end) by default
    EXCLUDE USING gist (room_id WITH =, during WITH &&)
);

-- every booking in room 7 overlapping a window
SELECT * FROM booking
WHERE room_id = 7 AND during && tstzrange('2026-10-05 10:00+00', '2026-10-05 11:00+00');

In memory, pick the balanced tree your platform already has. If your language offers an augmentable ordered map or a red-black tree with rotation callbacks, add the max_hi field there instead of maintaining a separate treap. Java and C++ standard maps do not expose rotations, so you either write your own tree or use a sorted container plus a different query strategy.

Mind the recursion and the memory. The Python above recurses, which is fine at treap depths of a few dozen, but an unbalanced plain BST built from sorted input degenerates to a list and overflows the stack. Each node carries five fields plus object overhead; for tens of millions of mostly static intervals, a sorted array with an implicit tree layout is far more compact than pointer-linked nodes.

Concurrency. A shared interval tree needs a lock, or a persistent (copy-on-write) variant where writers build new root paths and readers keep the old root. Check-then-insert for bookings must happen under the same lock, or two requests that both saw a free slot will both insert.

Failure modes

• Closed and half-open logic mixed. A query written as lo <= qhi against half-open data reports adjacent bookings as conflicts. Choose one convention, document it at the type, and convert at the boundary.
• Stale augmentation. Forgetting to recompute max_hi after a rotation or an in-place edit of hi makes pruning skip live intervals. The symptom is occasional missing results, never an exception. Never mutate an interval in place; delete and reinsert.
• Wrong order inside a rotation. The node that moves down must be recomputed before the node that moves up, because the parent's value depends on the child's.
• Unbalanced base tree. Inserting time-ordered intervals into a plain BST yields a linked list and O(n) queries. Always use a self-balancing base.
• Report-all used where existence was needed. Collecting thousands of overlaps to test emptiness wastes time; add an early-exit variant.
• Empty intervals. An interval with lo equal to hi overlaps nothing under the half-open rule. Reject it at input, or decide explicitly what a zero-length event means.

What to do next

1. Write down the interval convention, closed or half-open, and the overlap test in one helper function that every query calls.
2. If the intervals live in PostgreSQL, use a range type, a GiST index and, for no-overlap rules, an exclusion constraint before writing any tree code.
3. Otherwise, port the treap above or add a max_hi field to an existing balanced tree, recomputing it in every rotation, child first.
4. Build a brute-force oracle and run random insert, delete and query sequences against it, asserting max_hi at every node after each operation.
5. Add an early-exit existence query for conflict checks and keep the report-all query for listings.
6. If the set is static and point queries dominate, benchmark a centred interval tree; if you need aggregates over a fixed range, use a segment tree.