# Interval Tree Search

# Interval Tree Search

Interval tree search finds all intervals that overlap a given query interval. It extends a binary search tree by storing interval metadata at each node to support efficient range queries.

Each node represents an interval and maintains auxiliary information to guide pruning during search.

## Problem

Given a set of intervals and a query interval $[q_l, q_r]$, find all intervals $[l, r]$ such that:

$$
l \le q_r \ \text{and} \ r \ge q_l
$$

This is the standard overlap condition.

## Structure

Each node stores:

| field             | meaning                           |
| ----------------- | --------------------------------- |
| interval $[l, r]$ | stored interval                   |
| max_r             | maximum right endpoint in subtree |
| left              | left child                        |
| right             | right child                       |

The key property is:

$$
max_r = \max(r, max_r(left), max_r(right))
$$

## Algorithm

Search starts at the root and prunes subtrees that cannot contain overlapping intervals.

```text id="it0k7q"
interval_tree_search(node, ql, qr, result):
    if node == null:
        return

    if node.left != null and node.left.max_r >= ql:
        interval_tree_search(node.left, ql, qr, result)

    if node.interval overlaps [ql, qr]:
        add node.interval to result

    if node.right != null and node.interval.l <= qr:
        interval_tree_search(node.right, ql, qr, result)
```

## Example

Intervals:

```text id="it1m8v"
[15, 20], [10, 30], [17, 19], [5, 20], [12, 15], [30, 40]
```

Query:

$$
[14, 16]
$$

Overlapping intervals:

| interval | overlap |
| -------- | ------- |
| [15, 20] | yes     |
| [10, 30] | yes     |
| [12, 15] | yes     |

## Correctness

An interval overlaps the query if and only if it satisfies:

$$
l \le q_r \land r \ge q_l
$$

The tree stores $max_r$ in each subtree, which represents the furthest right endpoint reachable below that node.

If $max_r < q_l$, no interval in that subtree can overlap the query, so pruning is safe.

Traversal ensures that every subtree that could contain overlapping intervals is visited, and every visited interval is checked explicitly. Therefore all overlapping intervals are found and no non-overlapping interval is incorrectly included.

## Complexity

Let $n$ be the number of intervals and $k$ be the number of reported results.

| case                     | time            |
| ------------------------ | --------------- |
| search                   | $O(\log n + k)$ |
| worst case (all overlap) | $O(n)$          |

Space complexity:

| version   | space  |
| --------- | ------ |
| recursive | $O(h)$ |

where $h$ is tree height.

## When to Use

Interval trees are useful when:

* you need fast overlap queries
* intervals are dynamic (insert/delete supported)
* scheduling, compilers, or computational geometry tasks are involved
* range conflict detection is required

Compared to segment trees, interval trees handle arbitrary intervals more naturally without discretization.

## Implementation

```python id="it2q9n"
class Node:
    def __init__(self, interval):
        self.interval = interval
        self.max_r = interval[1]
        self.left = None
        self.right = None

def overlaps(a, b):
    return a[0] <= b[1] and a[1] >= b[0]

def interval_tree_search(node, ql, qr, result):
    if node is None:
        return

    if node.left and node.left.max_r >= ql:
        interval_tree_search(node.left, ql, qr, result)

    if overlaps(node.interval, (ql, qr)):
        result.append(node.interval)

    if node.right and node.interval[0] <= qr:
        interval_tree_search(node.right, ql, qr, result)
```

```go id="it3v6r"
type Interval struct {
	L int
	R int
}

type Node struct {
	Int   Interval
	MaxR  int
	Left  *Node
	Right *Node
}

func overlaps(a Interval, ql, qr int) bool {
	return a.L <= qr && a.R >= ql
}

func IntervalTreeSearch(node *Node, ql, qr int, res *[]Interval) {
	if node == nil {
		return
	}

	if node.Left != nil && node.Left.MaxR >= ql {
		IntervalTreeSearch(node.Left, ql, qr, res)
	}

	if overlaps(node.Int, ql, qr) {
		*res = append(*res, node.Int)
	}

	if node.Right != nil && node.Int.L <= qr {
		IntervalTreeSearch(node.Right, ql, qr, res)
	}
}
```