Overlap Search in Augmented BST

To find any interval overlapping with query $[l, r]$:

function findOverlap(node, l, r)
    if node is null then
        return null

    // Check current node
    if overlaps(node.interval, [l, r]) then
        return node.interval

    // Prune using maxHigh
    if node.left is not null and node.left.maxHigh >= l then
        result := findOverlap(node.left, l, r)
        if result is not null then
            return result

    // Only go right if left can't help
    return findOverlap(node.right, l, r)

The maxHigh check is the key: if the left subtree's maximum high endpoint is less than $l$, no interval in the left subtree can overlap $[l, r]$.

Time: $O(\log n)$ to find one overlapping interval.