An interval tree is a binary tree where each node stores:
A center point
All intervals that contain
Left subtree: intervals entirely to the left of
Right subtree: intervals entirely to the right of
class IntervalTreeNode:
mid: int
center: list of intervals containing mid
left: IntervalTreeNode
right: IntervalTreeNode
The center list is sorted in two ways:
- By low endpoint (for queries from the left)
- By high endpoint (for queries from the right)
This dual sorting is the key to efficient queries.