#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/interval-trees/finding-all-overlaps

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/interval-trees/finding-all-overlaps

Repovive

Finding All Overlaps - Interval Trees | Data Structures | Repovive

Repovive.

Data Structures19 sections · 729 units49h total

Open in Course

Finding All Overlaps

Report all results

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.