Interval tree: find all intervals containing a given interval 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 &gt; 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$?
Hint: A (non-root) interval can only contain I if its parent contains I. 

For the algorithm in the pseudo-code below, TestInterval is not called for the same vertex twice, so the complexity is $O(n)$.

Consider the subtree S consisting of all nodes which TestInterval is called on. At every node in S which is not a leaf node, an interval must have been added to intervalContainingI (and k incremented). A binary tree with k non-leaf nodes can have at most $k+1$ leaf nodes. Therefore the complexity is in fact $O(k)$.

vector&lt;int&gt; intervalsContainingI;

void TestInterval(interval x)
{
    if (x.start &lt;= I.start &amp;&amp; x.end &gt;= I.end)
    {
        intervalsContainingI.push_back(x);
        if (Exists(x.leftChild))
        {
            TestInterval(x.leftChild);
        }
        if (Exists(x.rightChild)
        {
             TestInterval(x.rightChild);
        }
    }
}

TestInterval(root_node);