Augmented BST Approach

Another way to implement interval trees: augment a BST with max-endpoint information.

Each node stores:

• An interval $[\text{low}, \text{high}]$
• The maximum high endpoint in its subtree

class AugmentedNode:
    interval: Interval
    maxHigh: int  // max high in subtree
    left: AugmentedNode
    right: AugmentedNode

The tree is ordered by low endpoint (standard BST property). The maxHigh augmentation enables efficient overlap queries.

This approach is simpler to implement than the center-point interval tree and integrates well with self-balancing BSTs.