Interval Tree: Every Clashing Event, Found at Once

An interval tree is a search tree for data represented by a beginning and an ending value. Meeting times are the natural example: each meeting occupies an interval, and a calendar may need to answer questions such as:

• Which meetings include 10:30?
• Which meetings overlap 14:30–15:30?
• Which meetings include 12:00?

The central idea is to combine two kinds of information in every node:

1. The tree is ordered by interval start, just like a binary search tree.
2. Each node stores the latest end value anywhere in its subtree.

The start value supports ordinary search-tree decisions. The latest end value, often called maxEnd, supports interval-specific pruning. It lets the search reject an entire subtree when every interval in that subtree ends too early to overlap the query.

This extra summary is what makes the structure useful. A tree ordered only by starts can tell us that intervals begin earlier or later, but it cannot tell us how far an earlier interval extends. An interval that begins well before a query might still continue into it. The subtree maximum end captures exactly that missing information.

This article follows the five-meeting calendar described in the video. The source description does not provide the meeting names or all five exact endpoints, so the examples below use the stated query times and symbolic intervals rather than inventing a particular calendar.

1. Intervals and overlap​

An interval has a start value $s$ and an end value $e$:

For a meeting, $s$ and $e$ are times. For a numeric range, they could be numbers. The interval covers the values between its start and end.

A point query asks whether a stored interval contains one value, such as $q$. Under the usual inclusive-endpoint convention, the interval contains the point exactly when

Therefore, an interval beginning at the queried time matches, and an interval ending at the queried time also matches.

A real calendar can use a different convention. For example, it may treat an event ending exactly when another event begins as non-conflicting. That policy changes the comparison operators, but not the tree shape or the purpose of maxEnd. The implementation must use one endpoint convention consistently in both matching and pruning decisions.

A range query asks which stored intervals overlap a query interval

where $q_\ell$ is the query start and $q_r$ is the query end. A stored interval $[s,e]$ overlaps the query when it begins no later than the query ends and finishes no earlier than the query begins:

This condition covers all normal overlap patterns. The stored interval might start before the query and continue into it, lie completely inside it, begin inside it and continue beyond it, or cover the entire query.

The same idea can be expressed by describing when two intervals do not overlap. They are disjoint if one is entirely before the other:

The overlap test is the negation of that disjointness condition, assuming inclusive endpoints.

A point query is simply a special case of a range query. Represent point $q$ as the zero-length interval $[q,q]$. Substituting $q_\ell=q_r=q$ into the general condition gives

which is the same point-containment test.

2. The basic tree shape​

At its foundation, an interval tree is a binary search tree. Every node stores an interval and has a left child and a right child. The ordering key is the interval's start value.

For a node containing $[s,e]$:

• intervals in the left subtree have earlier start values;
• intervals in the right subtree have later start values;
• intervals with equal starts require a consistent tie-breaking policy.

The exact policy for equal starts is not specified in the source description. An implementation might order equal starts by end value, place equal keys consistently on one side, or store multiple intervals in one node. The important requirement is consistency during insertion, deletion, and searching.

The start ordering immediately gives one useful pruning rule. If the current interval begins after the query ends, then every interval in the right subtree begins even later. None of them can overlap the query.

However, start ordering alone does not provide a safe rule for discarding the left subtree. Every interval in the left subtree begins earlier than the current interval, but an earlier start does not imply an earlier end. One of those intervals could extend a long way into the future and overlap the query.

The interval tree adds a summary value to solve this problem.

3. The maxEnd augmentation​

Each node stores the largest end value among all intervals in its subtree. Call this field maxEnd.

For a node $v$ storing interval $[s_v,e_v]$, with left child $L$ and right child $R$, the invariant is

An empty child contributes no interval. In code, that case can be handled explicitly or represented by a sentinel smaller than every valid end value.

The key invariant is:

The maxEnd value at a node is exactly the latest end among the node's interval and every interval below that node.

This invariant is local to each node. Once the values for the children are correct, the parent can compute its own value from three candidates: its own end, the left-child summary, and the right-child summary.

For example, suppose a node stores an interval ending at 13:00. Its left subtree has maxEnd 15:30, and its right subtree has maxEnd 14:00. The node's summary is

The node does not need to inspect every interval below it. It relies on the summaries already maintained by its children.

This illustrates a general data-structure pattern: keep the normal ordering information needed for navigation, then add a compact aggregate that answers an important question about a whole subtree.

4. Why maxEnd safely prunes the left subtree​

Suppose a search is looking for intervals that overlap a query beginning at $q_\ell$. Consider a left subtree whose maximum end is earlier than the query start:

Because maxEnd is the largest end anywhere in that subtree, every interval in the subtree ends before $q_\ell$. Therefore, every interval lies completely before the query begins. No interval in that subtree can overlap the query.

The entire left subtree can be skipped in one decision.

This is a proof-based pruning rule, not a guess. The conclusion follows directly from the invariant. If the maximum end is too small, every individual end is also too small.

For a point query at $q$, the query start is $q$, so the condition becomes

Every interval in that left subtree ends before the point and therefore cannot contain it.

Why is this information needed? Start ordering tells us only that left-subtree intervals start earlier. They may end before the query, or they may extend through it. The maximum end tells us whether any interval in the subtree reaches far enough right to remain possible.

If the maximum is below the query start, the answer is definitely no. If the maximum reaches the query start, the subtree may contain a match and must be searched.

5. Why start ordering safely prunes the right subtree​

Now consider the right subtree. If the current node starts at $s$, every interval in the right subtree starts at least as late as $s$, according to the tree's ordering policy.

If

then the current interval starts after the query ends. It cannot overlap the query. More importantly, every interval in the right subtree starts even later, so none of them can overlap either. The right subtree can be discarded.

For a point query, $q_\ell=q_r=q$, and the condition becomes

Once a node starts after the queried time, all intervals to its right start too late to contain that point.

The two pruning rules rely on different facts:

• The left subtree is pruned using the subtree's maximum end.
• The right subtree is pruned using the ordering of start values.

This distinction is essential. A current node that does not match does not automatically make both children irrelevant. Each child must be considered according to the information that proves whether it can still contain a match.

6. The complete overlap traversal​

For a query interval $[q_\ell,q_r]$, a conceptual recursive search is:

search(node, queryStart, queryEnd):
    if node is empty:
        return

    if left child exists and left.maxEnd >= queryStart:
        search(left child, queryStart, queryEnd)

    if node.start <= queryEnd and node.end >= queryStart:
        report node.interval

    if node.start <= queryEnd:
        search(right child, queryStart, queryEnd)

The traversal shown is in-order: left subtree, current node, then right subtree. Consequently, reported matches appear in start order. The reporting order is not the important part, however. The crucial conditions are the pruning tests.

The left subtree is visited only if its maximum end reaches at least the query start. The current interval is reported only if it satisfies the overlap condition. The right subtree is visited only if the current start is no later than the query end.

For a point query at $q$, use queryStart = q and queryEnd = q. The current-node test becomes

For a range query, use the actual query start and end.

A search that needs only one match can stop as soon as it reports one. A search that must return every clashing meeting has to continue through every subtree that might still contain a match. Finding one answer does not prove that all other eligible branches are empty.

7. Query one: the point 10:30​

The first calendar query asks which meetings include 10:30. Treat the point as the interval

A stored meeting $[s,e]$ matches when

At every visited node, the search makes three decisions.

Search the left subtree​

Suppose the left child has a maxEnd earlier than 10:30. Then every meeting in that subtree finishes before 10:30. None can contain the point, so the whole subtree is skipped.

If the left child's maxEnd is at least 10:30, at least one interval might extend to the query time. The subtree remains eligible and must be searched.

Check the current meeting​

The current meeting is reported if it begins by 10:30 and ends at or after 10:30. A meeting beginning later is too late. A meeting ending earlier is already finished.

Search the right subtree​

If the current meeting starts after 10:30, every meeting in the right subtree starts even later. The right subtree cannot contain a meeting covering 10:30.

If the current start is at or before 10:30, a later-starting interval in the right subtree may still include 10:30. The right subtree therefore remains possible.

The traversal can return several meetings. The structure does not assume that a point belongs to only one interval. If multiple meetings cover 10:30, every eligible branch must be explored.

8. Query two: the interval 14:30–15:30​

The second query asks for every meeting overlapping the interval from 14:30 to 15:30:

A stored meeting $[s,e]$ matches when

This includes a meeting that starts before 14:30 and continues into the query, a meeting entirely inside the query, a meeting that begins during the query and ends after 15:30, or a meeting that covers the entire query.

For the left subtree, the relevant threshold is 14:30. If its maxEnd is earlier than 14:30, all meetings there finish before the requested interval begins. The subtree can be skipped.

For the right subtree, the relevant threshold is 15:30. If the current node starts after 15:30, every interval in the right subtree starts even later. None can overlap the query, so the right subtree can be skipped.

The current node can fail while a child succeeds. For example, the current interval may end before 14:30, but a later interval in its right subtree may overlap the query. Alternatively, the current interval may not match even though an earlier-starting interval in the left subtree extends into the query. This is why the traversal uses independent child tests rather than deciding solely from the current node's match result.

9. Query three: the point 12:00​

The third query asks which meetings include 12:00. Represent it as

The matching condition is

A left subtree can be discarded when its maximum end is earlier than 12:00. Every interval there has already ended by the time of the query.

A right subtree can be discarded once the current node starts after 12:00. All later starts are also too late.

Although this query has the same form as the 10:30 query, it may visit different nodes. The thresholds used for pruning depend on the query value, while the stored maxEnd values summarize the calendar's structure. The same tree can therefore answer many different point and range queries.

10. Insertion and invariant maintenance​

To insert a new interval, follow the ordinary binary-search-tree path based on its start value. Continue until the new node reaches its position according to the chosen equal-start policy.

After attaching the node, update maxEnd on the path from the new node back toward the root. At each ancestor, recompute the summary from the node's own end and its two child summaries:

Only ancestors of the inserted node can have changed subtrees. Nodes elsewhere still contain exactly the same intervals and retain their previous summaries.

If the tree height is $h$, insertion requires $O(h)$ time for the search and summary updates. In a balanced tree, $h=O(\log n)$, so insertion costs

for $n$ intervals. In an unbalanced tree, the height may grow to $O(n)$, making insertion $O(n)$ in the worst case.

The source description identifies the tree's ordering and augmentation but does not specify a balancing scheme. Therefore, the most general update bound is $O(h)$. The logarithmic bound applies when the implementation maintains logarithmic height.

11. Deletion and invariant maintenance​

Deletion follows the ordinary binary-search-tree process using start values and the equal-start policy. The node may be a leaf, have one child, or be replaced as required by the chosen deletion procedure.

After the structural change, recompute maxEnd for every affected ancestor. The same local formula restores the invariant:

Deletion therefore costs $O(h)$ for searching, changing pointers, and updating summaries. In a balanced tree this becomes $O(\log n)$; in an unbalanced tree it can become $O(n)$.

Updating pointers without updating maxEnd is a correctness error. The tree may still appear properly ordered by start, but an outdated maximum can cause the search to prune a subtree that actually contains an overlap. The interval-specific invariant is just as important as the ordinary search-tree invariant.

12. Query complexity​

Let $k$ be the number of intervals reported by an all-overlaps query. In terms of tree height, the query is commonly expressed as

where $h$ is the height of the tree and $k$ is the number of returned intervals. If the tree is balanced, $h=O(\log n)$, giving the output-sensitive form

The $k$ term matters because returning $k$ separate meetings requires time proportional to the output size. Even if the tree locates the relevant region quickly, it still has to produce each reported interval.

If the tree is unbalanced, its height may be $O(n)$, so the worst-case query cost can also be linear. The maxEnd augmentation improves pruning, but it does not itself guarantee logarithmic height.

For the five-meeting calendar, a direct scan would be small enough to be practical. The value of the interval-tree structure is conceptual as well as practical: it provides a reusable method for larger collections and makes each skipped subtree defensible from the stored invariant.

The space usage is $O(n)$. Every interval occupies one node, and each node stores a constant amount of additional information, including its maxEnd summary.

13. Why start ordering alone is not enough​

A start-ordered search tree can make a useful right-side decision. If a node starts after the query ends, everything to its right starts even later.

But the same ordering does not safely prune the left side. An earlier start does not imply an earlier end. Consider two intervals that both begin before a query: one may finish immediately, while the other may continue across the query. Their starts place them on the same side of the tree, but their ends determine whether they can overlap.

The maxEnd field answers the exact question needed for left-side pruning:

Does any interval in this subtree extend at least to the query's start?

If the answer is no, the whole subtree is irrelevant. If the answer is yes, the subtree may contain an overlap and must remain under consideration.

This is a broader design lesson. When the ordering key gives only partial information about the query, augment each subtree with an aggregate that answers the missing feasibility question.

14. Equal starts and endpoint conventions​

A practical implementation must document how intervals with identical starts are stored. The source description says that the tree is ordered by start but does not prescribe a tie-breaking method. Possible designs include:

• order equal starts by their end values;
• consistently place equal starts on one selected side;
• store a collection of equal-start intervals in one node.

Whatever policy is chosen, insertion, deletion, and traversal must use it consistently. The pruning logic must also respect it. For example, if equal-start intervals may appear in the right subtree, the right side should not be discarded when equality could still produce an overlap at the query endpoint.

Endpoint semantics must also be explicit. With inclusive endpoints, the overlap condition is

If an event ending exactly when another begins is considered non-overlapping, one or both comparisons must change. The maxEnd summary remains a maximum of end values, but the comparison used for pruning must agree with the chosen semantics.

The structure is independent of the calendar's policy, but the comparison details are not. A reliable implementation documents both the ordering policy and the endpoint policy.

15. Reporting every match versus finding one​

There are two related query tasks.

The first is an existence query: determine whether at least one stored interval overlaps the query. After finding a match, the algorithm can return immediately.

The second is a reporting query: return every stored interval that overlaps the query. This is the task suggested by finding every clashing event. The traversal must continue after finding a match and must search both children whenever their pruning conditions allow a possible answer.

The complexity reflects this distinction. A first-match query may stop early. An all-matches query must spend time producing all $k$ results, so an output-sensitive bound is appropriate.

A useful mental model is that pruning removes only impossible regions. It does not remove a region merely because another match has already been found. If a subtree still satisfies the conditions for possibly containing an overlap, it must be searched when completeness is required.

16. Symbolic walk-through of one node​

Suppose the current node stores $[s,e]$, its left subtree has summary $M_L$, and the query is $[q_\ell,q_r]$. The decisions are:

1. Search left if $M_L\ge q_\ell$.
2. Report the current interval if $s\le q_r$ and $e\ge q_\ell$.
3. Search right if $s\le q_r$.

For the point query at 12:00, substitute $q_\ell=q_r=12{:}00$:

For the interval query 14:30–15:30:

The tree does not need to be rebuilt for each query. Only the thresholds change. The stored starts and subtree maximum ends can be reused for every point or interval query.

17. Practical implementation checklist​

When implementing the interval tree for the five-meeting example or a larger calendar, verify the following:

• Every node stores an interval start and end.
• The search-tree ordering uses the start value.
• Equal starts have a documented and consistent policy.
• Every node stores the largest end in its complete subtree.
• A newly created node receives the correct maxEnd value.
• Insertion updates every affected ancestor.
• Deletion updates every affected ancestor.
• A point query is represented as a zero-length interval.
• A range query uses both its start and its end.
• The left subtree is pruned using its maxEnd value.
• The right subtree is pruned using start ordering.
• A current-node miss does not automatically justify skipping both children.
• An all-matches query continues through every subtree that may contain an answer.
• Endpoint comparisons are consistent in matching and pruning.
• The complexity claim identifies whether the tree is balanced.

These rules capture the essential correctness conditions without depending on a particular programming language or balancing implementation.

18. Main takeaways​

An interval tree is a binary search tree ordered by interval starts and augmented with one important summary: the latest end value in every subtree.

The two pruning mechanisms have different roles:

• maxEnd prunes a left subtree when every interval there ends before the query begins;
• start ordering prunes a right subtree when every interval there begins after the query ends.

A point such as 10:30 or 12:00 is handled as an interval whose start and end are equal. A range such as 14:30–15:30 uses the general overlap condition

Insertions and deletions must preserve the maxEnd invariant by updating summaries along the changed path. With tree height $h$, updates cost $O(h)$. If the tree is balanced, that becomes $O(\log n)$. An all-overlaps query costs $O(h+k)$ when it reports $k$ intervals, or $O(\log n+k)$ for a balanced tree.

The broader lesson is that a useful tree augmentation stores exactly the summary needed to prove that large regions cannot contain an answer. In a calendar, that turns overlap detection into a structured search: the algorithm reports every clashing event while skipping subtrees that are demonstrably irrelevant.