The goal
An interval tree answers a different question than the others: given a query interval, quickly find a stored interval that overlaps it. This is stabbing and overlap searching, useful for collision checks and calendar conflicts.
A balanced tree keyed by start
Build a balanced binary search tree ordered by each interval's start. By itself that only helps with starts, so you augment every node with one extra field: the maximum end found anywhere in that node's subtree. This single number is the key to fast pruning.
Searching for an overlap
Start at the root and at each node check whether the node interval overlaps the query. If it does, you are done. Otherwise decide which child to visit:
- If the left subtree exists and its stored maximum end is at least the query start, an overlap might hide there, so go left.
- Otherwise go right.
The augmented maximum end lets you safely skip an entire subtree whenever every interval in it ends before the query even begins.
Why the augmentation works
Because the tree is ordered by start and each node knows the farthest end below it, you can prove that if the left subtree cannot reach the query, no overlap exists on the left, so the right branch is the only place to look. That guarantees a single root to leaf style descent.
Key idea
An interval tree is a start ordered balanced tree augmented with each subtree maximum end, letting overlap searches prune whole subtrees and descend in logarithmic time.