Mastering Interval Tree: Theory and Implementation

1. Introduction and Core Concepts

An interval tree is a specialized data structure designed to efficiently store and query intervals, where each interval represents a continuous range with a low endpoint and a high endpoint, typically denoted as [low, high]. Unlike a standard binary search tree that stores discrete keys, an interval tree stores intervals as first-class objects and is optimized to answer questions such as: which intervals overlap a given point or interval, which intervals contain a query interval, or which intervals are stabbed by a query. This capability makes it indispensable in domains where overlapping ranges are the primary concern.

The fundamental challenge that an interval tree solves is the inefficiency of brute-force searching. If you store n intervals in an array or list and want to find all intervals overlapping [q_low, q_high], you must scan every interval, resulting in O(n) time per query. For large datasets with millions of intervals, such as genomic annotations, calendar events, or IP address ranges, this linear scan becomes prohibitively expensive. An interval tree reduces this to O(log n + k), where k is the number of reported overlaps, by organizing intervals in a balanced search tree augmented with additional information.

At its core, an interval tree is an augmented balanced binary search tree, most commonly an augmented AVL tree or Red-Black tree. The key augmentation is the max value stored at each node, which represents the maximum high endpoint among all intervals in the subtree rooted at that node. This single augmentation is what enables efficient pruning during search: if the maximum high value in a left subtree is less than the low endpoint of the query interval, we know with certainty that no interval in that entire subtree can overlap the query, and we can skip it entirely. This elegant idea transforms an ordinary ordered tree into a powerful geometric data structure.

What Defines an Interval?

In most implementations, intervals are considered closed, meaning both endpoints are inclusive: [low, high] where low <= high. Some variants support open or half-open intervals like [low, high) which are common in scheduling systems where an event ending at 10:00 does not overlap an event starting at 10:00. The choice of interval type affects the overlap condition. For closed intervals, two intervals [l1, h1] and [l2, h2] overlap if and only if l1 <= h2 and l2 <= h1. This simple condition is the predicate evaluated during every query.

Intervals are typically ordered by their low endpoint, and secondarily by high endpoint to break ties. This ordering determines the shape of the underlying binary search tree. It is important to understand that the interval tree does not store intervals in sorted order by max value; the max value is purely an augmentation for search pruning, not a search key. Confusing these two roles is a common source of implementation errors.

• Interval Object: A pair (low, high) with an optional payload or satellite data, such as an event ID, chromosome name, or associated value.
• Node Structure: Contains an interval, left and right child pointers, subtree max, and balancing information like height or color.
• Augmentation Invariant: For every node x, x.max = max(x.interval.high, x.left.max if exists, x.right.max if exists).
• Query Types: Stabbing query (point query), interval overlap query, and enclosing query are the three most common operations.

2. How It Works

The mechanism of an interval tree relies on two interlocking ideas: binary search tree ordering by low endpoint and max-augmentation for overlap pruning. When we insert intervals, we follow standard BST insertion logic comparing low endpoints. After insertion, we update the max values on the path from the inserted node back to the root, ensuring the augmentation invariant holds. If the underlying tree is self-balancing, we also perform rotations, and crucially, we must recalculate max values after each rotation.

Searching for overlapping intervals is where the structure shines. The algorithm for finding any overlapping interval starts at the root and proceeds recursively. At node x with interval [l, h] and query interval [ql, qh], we first check if [l, h] overlaps [ql, qh]. If it does, we have found a result. Then we decide whether to search the left subtree: we do so only if the left child exists and its max >= ql. This condition is both necessary and sufficient for the existence of a potential overlap in the left subtree. If the left subtree cannot contain an overlap, we proceed to the right subtree, but only if the current node's low <= qh, because all intervals in the right subtree have low >= x.interval.low.

This pruning logic is remarkably effective. Consider a node whose left subtree has a max of 15, and the query is [20, 25]. Since 15 < 20, no interval in that entire left subtree can possibly extend far enough to reach 20, so the whole subtree is discarded without examination. Without the max augmentation, we would have no way to make this decision and would be forced to explore both subtrees blindly, degrading to linear time.

Augmented BST vs. Centered Interval Tree

There are two major families of interval trees that are often confused. The augmented BST described above, sometimes called the CLRS interval tree, is the most common and easiest to implement. It stores intervals directly in BST nodes ordered by low endpoint. The second family is the centered interval tree, which is a more complex structure that recursively partitions intervals around a center point. In a centered tree, each node stores a center value, a list of intervals overlapping the center sorted by low endpoint, and a list sorted by high endpoint, plus left and right subtrees for intervals completely to the left or right of the center.

The centered interval tree guarantees O(log n + k) query time for stabbing queries even in the worst case and is often faster in practice for static sets of intervals where queries are predominantly stabbing queries. However, it is more complex to implement and less efficient for dynamic insertions and deletions. The augmented BST approach supports dynamic operations more naturally because it inherits the balancing logic of AVL or Red-Black trees. For most software engineering applications with insertions and deletions, the augmented BST is the preferred choice.

Why Max Augmentation Works

The correctness of the pruning relies on a simple invariant: max is the supremum of high endpoints in the subtree. If we are searching for overlaps with [ql, qh], any interval [l, h] in the left subtree must satisfy l <= current node's l (due to BST ordering). For it to overlap, we need h >= ql and l <= qh. Since l is already small, the only condition that might fail is h >= ql. If the maximum h in the entire left subtree is still < ql, then every interval fails, and pruning is safe. This reasoning is the formal justification for the algorithm and should be understood before attempting to implement it.

3. Implementation

Implementing an interval tree from scratch requires careful handling of the augmentation during insertion, deletion, and rotation. Below is a complete, production-quality implementation based on an augmented Binary Search Tree. For simplicity, we first show an unbalanced version to illustrate the core logic, then extend it with AVL balancing. In practice, you should always use a balanced variant to guarantee logarithmic height.

The implementation consists of three parts: the Interval class, the Node class with max augmentation, and the IntervalTree class that manages operations. Pay close attention to the _update_max method and how it is called after every structural modification. Forgetting to update max after a rotation is the single most common bug that leads to missed query results.

class Interval:
    def __init__(self, low, high, data=None):
        if low > high:
            raise ValueError("low must be <= high")
        self.low = low
        self.high = high
        self.data = data  # payload, e.g., event name

    def overlaps(self, other):
        # Closed interval overlap: [l1, h1] overlaps [l2, h2] iff l1 <= h2 and l2 <= h1
        return self.low <= other.high and other.low <= self.high

    def __repr__(self):
        return f"[{self.low}, {self.high}]"

class ITNode:
    def __init__(self, interval):
        self.interval = interval
        self.max = interval.high
        self.left = None
        self.right = None
        self.height = 1  # for AVL balancing

    def _update_max(self):
        # max = max(self interval high, left max, right max)
        left_max = self.left.max if self.left else float('-inf')
        right_max = self.right.max if self.right else float('-inf')
        self.max = max(self.interval.high, left_max, right_max)

    def _update_height(self):
        left_h = self.left.height if self.left else 0
        right_h = self.right.height if self.right else 0
        self.height = 1 + max(left_h, right_h)

class IntervalTree:
    def __init__(self):
        self.root = None

    def insert(self, low, high, data=None):
        interval = Interval(low, high, data)
        self.root = self._insert(self.root, interval)

    def _insert(self, node, interval):
        if node is None:
            return ITNode(interval)
        # BST ordering by low, then high
        if interval.low < node.interval.low or \
           (interval.low == node.interval.low and interval.high < node.interval.high):
            node.left = self._insert(node.left, interval)
        else:
            node.right = self._insert(node.right, interval)

        # Update augmentation after recursion
        node._update_height()
        node._update_max()
        # Balance step (AVL) would go here
        return self._balance(node)

    def _balance(self, node):
        # Simplified AVL balance logic
        balance = self._get_balance(node)
        # Left Left Case
        if balance > 1 and self._get_balance(node.left) >= 0:
            return self._rotate_right(node)
        # Right Right Case
        if balance < -1 and self._get_balance(node.right) <= 0:
            return self._rotate_left(node)
        # Left Right Case
        if balance > 1 and self._get_balance(node.left) < 0:
            node.left = self._rotate_left(node.left)
            return self._rotate_right(node)
        # Right Left Case
        if balance < -1 and self._get_balance(node.right) > 0:
            node.right = self._rotate_right(node.right)
            return self._rotate_left(node)
        return node

    def _get_balance(self, node):
        if not node:
            return 0
        left_h = node.left.height if node.left else 0
        right_h = node.right.height if node.right else 0
        return left_h - right_h

    def _rotate_left(self, z):
        y = z.right
        T2 = y.left
        y.left = z
        z.right = T2
        z._update_height()
        z._update_max()
        y._update_height()
        y._update_max()
        return y

    def _rotate_right(self, z):
        y = z.left
        T3 = y.right
        y.right = z
        z.left = T3
        z._update_height()
        z._update_max()
        y._update_height()
        y._update_max()
        return y

    # --- Query Operations ---
    def find_any_overlap(self, low, high):
        """Return any interval overlapping [low, high] or None."""
        query = Interval(low, high)
        return self._search_any(self.root, query)

    def _search_any(self, node, query):
        if node is None:
            return None
        if node.interval.overlaps(query):
            return node.interval
        # Prune left subtree if its max < query.low
        if node.left is not None and node.left.max >= query.low:
            return self._search_any(node.left, query)
        # Otherwise search right (only if node.low <= query.high)
        if node.interval.low <= query.high:
            return self._search_any(node.right, query)
        return None

    def find_all_overlaps(self, low, high):
        """Return list of ALL intervals overlapping [low, high]."""
        query = Interval(low, high)
        result = []
        self._search_all(self.root, query, result)
        return result

    def _search_all(self, node, query, result):
        if node is None or node.max < query.low:
            return
        # Search left if it could contain overlap
        if node.left is not None:
            self._search_all(node.left, query, result)
        # Check current node
        if node.interval.overlaps(query):
            result.append(node.interval)
        # Search right only if current low <= query.high
        # (all intervals in right subtree have low >= node.interval.low)
        if node.interval.low <= query.high:
            self._search_all(node.right, query, result)

    # --- Deletion with Augmentation Maintenance ---
    def delete(self, low, high):
        target = Interval(low, high)
        self.root = self._delete(self.root, target)

    def _delete(self, node, target):
        if node is None:
            return None
        if target.low < node.interval.low or \
           (target.low == node.interval.low and target.high < node.interval.high):
            node.left = self._delete(node.left, target)
        elif target.low > node.interval.low or \
             (target.low == node.interval.low and target.high > node.interval.high):
            node.right = self._delete(node.right, target)
        else:
            # Found node to delete
            if node.left is None:
                return node.right
            elif node.right is None:
                return node.left
            else:
                # Two children: get inorder successor
                succ = self._min_value_node(node.right)
                node.interval = succ.interval
                node.right = self._delete(node.right, succ.interval)
        # Update augmentation on way back up
        if node is not None:
            node._update_height()
            node._update_max()
            node = self._balance(node)
        return node

    def _min_value_node(self, node):
        current = node
        while current.left is not None:
            current = current.left
        return current

    def inorder(self):
        """Utility to verify ordering and max values."""
        res = []
        def _in(root):
            if root:
                _in(root.left)
                res.append((root.interval, root.max, root.height))
                _in(root.right)
        _in(self.root)
        return res

The code above demonstrates the critical pattern: every function that modifies the tree structure must recalculate both height and max before returning. The rotation methods update the lower node (z) first, then the new root (y), because y's max depends on z's updated max. This ordering is essential for correctness.

4. Step-by-Step Example

Let us walk through a concrete example to solidify the theory. Suppose we insert the following intervals in order into an initially empty interval tree: [15, 20], [10, 30], [17, 19], [5, 20], [12, 15], and [30, 40]. We will use BST ordering by low endpoint and maintain max augmentation.

After inserting [15, 20], the root is [15, 20] with max = 20. Inserting [10, 30] goes to the left of 15, so left child is [10, 30] with max = 30, and root's max updates to max(20, 30) = 30. Inserting [17, 19] goes to the right of 15, right child is [17, 19] max = 19, root max remains 30. Inserting [5, 20] goes left of 15, then left of 10, so it becomes left child of [10, 30]. Node [10, 30] max becomes max(30, 20) = 30, root remains 30. Inserting [12, 15] goes left of 15, right of 10, so it becomes right child of [10, 30]. Node [10, 30] max remains 30. Finally, [30, 40] goes right of 15, right of 17, becomes right child of [17, 19]. Node [17, 19] max becomes max(19, 40) = 40, root max becomes max(20, 30, 40) = 40.

The resulting tree has root [15, 20] max 40, left subtree rooted at [10, 30] max 30, right subtree rooted at [17, 19] max 40. Now consider a stabbing query for point 14, which we model as interval [14, 14]. The search starts at root [15, 20]. Does [15, 20] overlap [14, 14]? No, because 15 > 14. Check left child max: left max is 30, which is >= 14, so we must search left. At node [10, 30], does it overlap [14, 14]? Yes, 10 <= 14 <= 30, so we report [10, 30] as an overlap. To find all overlaps, we continue: we search left of [10, 30] to node [5, 20], which also overlaps [14, 14] (5 <= 14 <= 20). We search right of [10, 30] to [12, 15], which also overlaps (12 <= 14 <= 15). The right subtree of the root is pruned correctly because root low 15 > 14? Actually for point query, the condition node.interval.low <= query.high (15 <= 14 is false) would prune the right subtree, but in our all-overlaps algorithm we still need to check because intervals in right subtree start at >=15, so they cannot overlap 14. Thus the algorithm correctly returns exactly three intervals without ever visiting [17, 19] or [30, 40].

Query Walkthrough for Interval [21, 23]

Now query [21, 23]. Start at root [15, 20]: does it overlap? No (20 < 21). Left child max = 30, which is >= 21, so search left. At [10, 30]: overlaps? Yes (10 <= 23 and 21 <= 30), so report it. Search left of [10,30] to [5,20]: 20 < 21, no overlap, and its children are None. Search right of [10,30] to [12,15]: 15 < 21, no overlap. Backtrack to root, now check right subtree condition: root low 15 <= 23 true, so search right to [17,19]: 19 < 21, no overlap. Search right of [17,19] to [30,40]: 30 > 23, no overlap (low > high). Final result is only [10, 30]. The pruning saved us from exploring nothing extra in this case, but in larger trees the savings are dramatic.

This walkthrough highlights two key behaviors: first, the max value allows us to skip entire subtrees that cannot possibly contain an answer, and second, the BST ordering by low allows us to prune the right subtree when the current node's low is already greater than the query's high. Both conditions must be implemented correctly to achieve logarithmic performance.

5. Complexity Analysis

The performance of an interval tree depends heavily on whether the underlying BST is balanced. With a balanced tree such as an AVL or Red-Black tree, the height is guaranteed to be O(log n), which underpins all logarithmic bounds. With an unbalanced BST, the worst case degrades to O(n) when intervals are inserted in sorted order, effectively forming a linked list. Therefore, any production implementation must use balancing.

For building the tree by inserting n intervals one by one, the total time is O(n log n) average and worst case with balancing, and O(n log n) average but O(n^2) worst case without balancing. Space consumption is always O(n) for storing n nodes, plus O(log n) recursion stack space for operations, or O(n) stack in the worst unbalanced case. The max augmentation adds only O(1) extra space per node, so the asymptotic space remains linear.

Query complexity is more nuanced. Finding any single overlapping interval takes O(log n) time in the worst case with a balanced tree, because we follow at most one path down the tree, pruning one child at each step. Finding all k overlapping intervals takes O(log n + k) time in the best case and O(log n + k) average, but can degrade to O(n) worst case if many intervals overlap or if the tree is unbalanced. The O(k) term is unavoidable because we must report k results. The key insight is that the search visits only nodes that are either on the search path or that contain a reported interval, plus a limited number of pruned subtrees.

It is worth noting that the worst case for find-all is linear when the query interval is large enough to overlap every interval in the tree, for example querying [0, 1000000] when all intervals lie within that range. In that scenario, k = n, so O(n) is optimal because we must output n intervals. The data structure does not magically avoid output-sensitive cost. The advantage is that when k is small, we avoid scanning the entire dataset, which is the common case in most applications.

Amortized and Expected Analysis

If intervals are inserted in random order into an unbalanced BST, the expected height is O(log n), so the expected query time remains logarithmic even without explicit balancing. However, relying on randomness is fragile for adversarial inputs, such as sorted genomic coordinates. Self-balancing guarantees deterministic performance regardless of input order. The augmentation maintenance adds only constant factor overhead: each rotation and each update does O(1) work to recompute max, so it does not change asymptotic complexity.

6. Variations and Optimizations

Several important variants of the interval tree have been developed to optimize for different workloads. The choice of variant depends on whether the interval set is static or dynamic, whether queries are predominantly stabbing or interval-overlap, and whether memory or speed is the primary constraint.

The centered interval tree, as mentioned earlier, is optimized for static sets and stabbing queries. It chooses a center point, typically the median of all endpoints, and partitions intervals into three groups: those overlapping the center, those entirely to the left, and those entirely to the right. Intervals overlapping the center are stored in two sorted lists at the node, one sorted by low and one by high, which allows efficient stabbing queries by binary search. This structure achieves O(log n + k) worst-case stabbing query time with lower constant factors than the augmented BST for static data, but it is expensive to update dynamically because inserting a new interval may require rebalancing the center.

Another optimization is the interval tree with lazy propagation for range updates, often combined with segment tree ideas. If intervals have associated values and queries ask for the maximum value over overlapping intervals, we can augment nodes with lazy tags to support range updates in O(log n). This hybrid is common in scheduling systems where we need to know the maximum number of overlapping bookings at any point.

Memory and Cache Optimizations

For large n, cache performance becomes critical. A standard pointer-based tree suffers from poor locality. An optimized approach is to store intervals in an array-based balanced BST, such as a sorted array with implicit heap indexing, or to use a B-tree variant like an interval B-tree for external memory. The interval B-tree groups multiple intervals per node to improve I/O efficiency, which is crucial for databases that store intervals on disk.

Another practical optimization is to use iterative search instead of recursion to avoid stack overflow for deep trees and to reduce function call overhead. Additionally, storing intervals with integer endpoints allows for specialized, faster overlap checks without object overhead. In Python, using __slots__ in the Node class can significantly reduce memory per node when n is in the millions.

• Augmented AVL vs. Red-Black: AVL trees are more strictly balanced, giving slightly faster queries but slower inserts; Red-Black trees give faster inserts with slightly slower queries. Choose based on read/write ratio.
• Nested Intervals: If intervals are known to be nested or non-overlapping, a simpler structure like an interval set using a sorted list with binary search may be faster due to lower overhead.
• Persistence: Persistent interval trees, where updates create new versions without mutating old ones, are useful for temporal databases and functional programming, implemented via path copying.
• Parallel Queries: For batch queries, the tree can be queried in parallel by traversing different subtrees concurrently, especially effective for find-all queries where k is large.

7. Real-World Applications

Interval trees are not merely academic; they power critical systems across industries. Their ability to answer overlap queries efficiently makes them the default choice whenever ranges intersect.

In computational genomics, interval trees are ubiquitous. Genomic features such as genes, exons, and regulatory elements are represented as intervals on a chromosome coordinate system. A common task is to find all genes overlapping a sequencing read or a variant interval. Tools like BEDTools and genome browsers use interval trees to answer millions of such queries per second. Without this structure, annotating a whole-genome sequencing experiment would take hours instead of seconds.

In operating systems and databases, interval trees manage resource allocation. The Linux kernel uses an interval tree (actually a Red-Black tree augmented with max) to manage virtual memory areas (VMAs). Each VMA is an interval of virtual addresses, and the kernel must quickly find VMAs overlapping a faulting address or merging new mappings. Similarly, databases use interval trees for temporal data, where each row has a validity interval [start_time, end_time], and queries ask for all rows valid at a given time or overlapping a time range. This is the foundation of bi-temporal databases and slowly changing dimensions.

Network infrastructure relies heavily on interval trees for IP routing and firewall rules. IP prefixes and firewall rules are intervals of IP addresses. A router must find the longest prefix match or all rules overlapping a packet's destination address. While tries are used for longest prefix match, interval trees are used for range-based firewall and access control lists where rules are arbitrary [low_ip, high_ip] ranges. Geographic information systems (GIS) use interval trees as a component of higher-dimensional structures like R-trees for window queries.

In web servers and application logic, interval trees solve scheduling and resource contention problems. For example, a booking system for conference rooms, hotel reservations, or ad slot allocation must ensure no double-booking. An interval tree can check for conflicts in logarithmic time before confirming a reservation. Similarly, in computational geometry, the classic sweep-line algorithm for finding all intersecting line segments uses an interval tree to maintain the active set of segments intersecting the sweep line.

8. Comparison with Alternatives

Choosing the right data structure for interval queries depends on the specific query type, whether the dataset is static or dynamic, and the dimensionality of the data. The interval tree is one of several options, each with distinct trade-offs. The most common alternatives are the segment tree, sweep line with sorted lists, brute-force linear scan, and balanced BST without augmentation.

A segment tree is often confused with an interval tree but serves a different purpose. A segment tree is built over the elementary intervals defined by all distinct endpoints, and each node stores intervals that completely cover its segment. It is excellent for stabbing queries and for queries that ask for aggregated information over intervals, such as the total covered length or maximum overlap count. However, it requires O(n log n) space and is more complex to implement dynamically. It is typically used for static sets where endpoints are known in advance and coordinate compression is possible.

A brute-force approach using a sorted list and binary search can be surprisingly competitive for small n or for static sets with infrequent queries. If you store intervals sorted by low endpoint, you can binary search to find the first interval with low <= query.high, then scan forward until low > query.high. This is O(log n + k + m) where m is the number of non-overlapping intervals scanned that happen to have low within range but high too small. In the worst case, m can be O(n), so it degrades to linear. Sweep-line algorithms are optimal for offline problems where all intervals and queries are known upfront, allowing you to sort all endpoints and sweep once in O((n+q) log (n+q)).

In practice, for dynamic workloads with interleaved inserts, deletes, and queries, the interval tree is almost always the best choice due to its optimal theoretical bounds and relatively simple implementation. For static workloads where you need to answer many stabbing queries and also compute aggregates like total coverage, a segment tree may be superior. For one-dimensional intervals, an interval tree is preferred; for multi-dimensional rectangles, you would need an R-tree or interval tree extension.

9. Common Mistakes and Best Practices

Even experienced developers make subtle errors when implementing interval trees. The most frequent mistake is failing to maintain the max augmentation correctly after structural changes. This includes forgetting to update max after insertion, after deletion, and crucially after rotations. A rotation changes the subtree composition of two nodes, so both nodes must have their max recalculated in the correct order, from bottom to top. An incorrect max leads to incorrect pruning, which manifests as false negatives where overlapping intervals are not reported, a bug that is hard to detect with small tests.

Another common pitfall is using the wrong overlap condition. For closed intervals, the condition is low1 <= high2 and low2 <= high1. For half-open intervals [low, high), the condition is low1 < high2 and low2 < high1. Mixing these up causes off-by-one errors, especially in scheduling systems where an interval ending at 10:00 should not be considered overlapping with one starting at 10:00. Always explicitly define and document whether your intervals are open or closed, and write unit tests for boundary cases like adjacent intervals and zero-length intervals where low == high.

A third mistake is incorrect BST ordering. The tree must be ordered by low endpoint, not by max or by high. Ordering by max destroys the pruning logic's correctness proof. When lows are equal, you must have a deterministic tie-breaker, typically by high endpoint, to ensure the BST property holds and to make deletion well-defined. Without a tie-breaker, duplicate lows can cause infinite loops or lost intervals.

Best Practices for Production Code

• Always Use a Balanced Tree: Never deploy an unbalanced interval tree to production. Use AVL or Red-Black balancing, or use a library implementation that guarantees balance. Test with sorted input to verify balance.
• Encapsulate Augmentation: Make _update_max and _update_height private methods and call them in exactly one place after every modification. Consider asserting the invariant in debug builds by traversing the tree and verifying max values.
• Handle Duplicates Explicitly: Decide whether your tree allows duplicate intervals. If it does, ensure insertion and deletion handle duplicates correctly, perhaps by storing a count or list of payloads per node.
• Test Pruning Logic Thoroughly: Write property-based tests that compare interval tree query results against brute-force linear scan for thousands of random intervals and queries. This is the best way to catch augmentation bugs.
• Consider Iterative Implementation: For very deep trees or languages with limited recursion depth like Python, implement search iteratively to avoid recursion limit errors. Python's default recursion limit is 1000, which can be exceeded with n > 1000 in an unbalanced tree.
• Document Interval Semantics: Clearly state in your API whether intervals are closed, open, or half-open, and whether endpoints are inclusive. Provide examples in docstrings.

Finally, consider using existing well-tested libraries for production use, such as bisect with sorted lists for small n, or the intervaltree package in Python for large n, rather than rolling your own. If you do implement your own, invest heavily in testing, especially for deletion, which is the most complex operation to get right with augmentation.

10. Interview Questions

Interval trees are a favorite topic in technical interviews for roles involving systems design, databases, or algorithms. Interviewers use them to test understanding of tree augmentation, complexity analysis, and practical trade-offs. Below are common questions and how to approach them.

Question 1: How do you find all intervals overlapping a given interval?

Expected Answer: Explain the augmented BST approach. Describe the overlap condition (l1 <= h2 and l2 <= h1) and the pruning condition using max. Walk through the recursive algorithm: check current node for overlap, recurse left if left.max >= query.low, recurse right if node.low <= query.high. State the complexity as O(log n + k) average and O(n) worst case when all intervals overlap. Be prepared to write the _search_all code on a whiteboard and to explain why the pruning is safe. A strong candidate will also mention the need for a balanced tree and the maintenance of max after rotations.

Question 2: How does an interval tree differ from a segment tree? When would you choose one over the other?

Expected Answer: Clarify that an interval tree stores intervals in BST nodes ordered by low and augments with max, using O(n) space and supporting dynamic operations in O(log n). A segment tree is built over the set of elementary intervals defined by all endpoints, stores intervals that span a node's segment, uses O(n log n) space, and is typically static. Choose interval tree for dynamic sets with frequent inserts/deletes and general overlap queries. Choose segment tree for static sets where you need range aggregates like total covered length or maximum overlap count, or when you need to answer stabbing queries with coordinate compression. Mention that segment trees are better for offline, batched queries.

Question 3: How would you design a calendar system to detect scheduling conflicts?

Expected Answer: Model each booking as an interval [start, end) with half-open semantics to allow back-to-back bookings. Use an interval tree keyed by start time, augmented with max end time. To check if a new interval [s, e) conflicts, query the tree for any overlap with [s, e). If the query returns non-empty, there is a conflict. Insertion is O(log n), conflict check is O(log n). Discuss handling of time zones, recurring events, and persistence. Extend the discussion to finding all conflicts or finding the next available slot, which requires an additional search for gaps. Mention that for a single user's calendar with few events, a sorted list may be simpler, but for a system with millions of bookings, the interval tree is necessary.

Question 4: What is the max augmentation and why is it necessary? What happens if it is not maintained?

Expected Answer: Define max as the maximum high endpoint in the subtree rooted at a node. Explain that it enables pruning: if left.max < query.low, no interval in the left subtree can overlap the query, so the entire subtree can be skipped. Without max, you would have to search both subtrees at every node, leading to O(n) query time even when k is small. If max is stale after insertion/deletion/rotation, the pruning becomes incorrect, leading to false negatives (missed overlaps) if max is too small, or inefficiency (unnecessary traversal) if max is too large. Emphasize that max must be updated bottom-up after every modification and after every rotation, in the correct order.

Question 5: How do you delete an interval from an interval tree and maintain correctness?

Expected Answer: Describe standard BST deletion by cases: leaf, one child, two children (replace with inorder successor). After the structural deletion, walk back up the recursion stack updating height and max at each ancestor, then rebalance if using AVL/Red-Black. Stress that max must be recalculated after deletion and after any rotations triggered by rebalancing. Provide complexity O(log n) for balanced tree. Mention the need for a tie-breaker when lows are equal to uniquely identify the node to delete, and discuss handling of duplicate intervals. A strong answer will note that deletion is the trickiest operation and requires careful testing against brute force.

Preparing for these questions involves not just memorizing the algorithms but understanding the invariants, being able to code the augmentation maintenance, and articulating trade-offs with alternative structures. Practice implementing the tree from scratch without referencing material, and be ready to analyze complexity in terms of both n and k.