To find any interval overlapping with query :
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 , no interval in the left subtree can overlap .
Time: to find one overlapping interval.