Given an interval tree $T$ and an interval $I$, I need to find an algorithm that returns all intervals in $T$ that contain $I$. The asymptotic running time should be $O(min(n,(k + 1) log n))$ where $k$ is the number of intervals returned. The only solution I can think of is bruteforcing in $O(n)$ time, but that's clearly too simple.
While looking for an answer I came across stabbing queries and the problem seemed very similar to this one. Is this something I could base my algorithm on or am I on the wrong track?
Edit: I might have an idea, but I'm still missing something.
Let $I=[I_s,I_e]$ and $x$ a node. If $x.s \leq I.s$ then there is an interval that contains $I$ in the left subtree of $x$ if and only if $left[x].max\geq I.e$. Suppose you had a similar statement for the right subtree of $x$, then you could do the following:
If the condition for the left or/and subtree is satisfied, recurse on those trees. Since there must be an interval covering $I$ in these subtrees this will result in $k$ paths with a maximum length of $logn$.
If $x.s > I.s$ there can't be an interval in the right subtree that covers $I$, but there might be one in the left, so recurse on left. If this happens repeatedly until you find a leaf, you get a path of length $logn$ without finding anything.
My question is: given $x.s \leq I.s$, how can I know for sure whether the right subtree of $x$ contains an interval covering $I$?