Finding All Overlaps

To find all intervals overlapping with $[l, r]$:

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

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

    // Check left if possible overlaps exist
    if node.left is not null and node.left.maxHigh >= l then
        findAllOverlaps(node.left, l, r, results)

    // Check right if possible overlaps exist
    if node.right is not null and node.interval.low <= r then
        findAllOverlaps(node.right, l, r, results)

You explore both subtrees when necessary. The pruning conditions prevent exploring subtrees that can't contain overlapping intervals.

Time: $O(\log n + k)$ where $k$ is the number of overlapping intervals.