List all overlapping intervals efficiently

Question

Let T be a given interval tree (of size n) and i be an interval. Let k be the number of intervals in T that overlap i. I need to find an algorithm to list all of them in time O(min(n, k log n)).

Answer 1

Generally, you just need to traverse the tree and stop whenever you got k overlapping intervals.
Lets mark the range you are currently checking by t, then you will need to check t against i as follows.
The first interval is t and the second is your i.

|------|
  |--|

Add t and you can stop iterating.

  |--|
|------|

Add t and go both left and right.

    |------|
  |---|

Add t and go only left

|------|
     |---|

Add t and go only right

      |------|
|---|

Go left (without adding t)

|------|
         |---|

Go right (without adding t)