Skip to main content

Interval Tree

Learn Interval Tree (Advanced Data Structures, Advanced DSA) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.

Interval Tree: Finding Overlapping Intervals Given many intervals such as meeting times or genomic regions, " which stored intervals overlap [l, r]? " needs more than a list scan. An interval tree is a binary search tree ordered by the interval's start , where every node also stores max : the largest end in its subtree. A query skips the left subtree when left.max < l (nothing there reaches l) and the right subtree when node.start > r . With a balanced tree a query costs O(log n + k) for k results.

More lessons in Advanced Data Structures