Lookup complexity in augmented interval tree If we consider the following problem: 
Stream of intervals, coming in one at a time, which we maintain in an augmented interval tree (Interval tree). At some point in time later, we get a point, 
and are asked to return all intervals covering that point.

What is the complexity of the above lookup operation?

PS : This is not a homework question, but was an interview question.
Let $p$ be the query point, and assume the interval tree is sorted by lower endpoint and each node stores the maximum endpoint in its subtree.

Perform a tree-walk and stop the recursion whenever the lower endpoint of the current node is greater than $p$, or the maximum is smaller than $p$.
Now at most one downward path (of length $O(\log n)$) reports no interval, namely the path that would be taken by binary searching the lowest endpoints for $p$.

Illustrated example:

Consider this interval tree and query point, the rightmost path visited by the pruned tree-walk is the path of orange nodes (which may not contain a reported interval if their maximum endpoints are all less than $p$).
All intervals in the right subtrees have a minimum endpoint greater than $p$ so can be ignored.
However, all intervals in left subtrees (red) of this path have minimum endpoint at most $p$. This means we are sure to report an interval for each (red) subtree (and subtrees thereof) whose maximum endpoint (over the entire subtree) is at least $p$.

Then, whenever we report a subsequent interval, we do so within $O(\log n)$ time.
Since there are $m$ such intervals, this amounts to $O((m+1)\log n)$ time.
Because we prune a tree-walk we also have an upper bound of $O(n)$ time.
This reduces to $O(n)\cap O((m+1)\log n)=O(\min(n,(m+1)\log n))$ time.