Asymptotic runtime for querying an interval tree Suppose that we have an array of size n and we want to build an interval tree for all possible ranges that can be created inside this array. So in our leafs we have the ranges [0], [1], [2], [3], ... , [n], and merging two of them together we end up having the root node holding the range [0, n]. For example we have the following interval tree for an array of size 6.



The total amount of nodes is O(n).

I'm trying to understand what's the maximum posible  root - internal node paths that we need to make in order to answer a query on any range. I know that the total amount of nodes that we are going to visit for any query is in the order of log n but I can't see why, which is the reason why I'm asking this question.

For example in the picture above, for the query [1, 4] we will do the following visits:

[0,5] =&gt; [0,2] =&gt; [0,1] =&gt; [1] =&gt; [0,1] =&gt; [0,2] =&gt; [2] =&gt; [0,2] =&gt; [0,5] =&gt; [3,5] =&gt; [3,4] =&gt; [3,5] = &gt; [0,5] =&gt; end

We have to travel from the root to some other internal node 3 times in total.

Now let's see a different example:



If our query is [1, 8] we will have to do 4 root to some other internal node paths, so this doesn't look constant to me, it was 3 before, now it's 4.

So I can't understand why querying in an interval tree is O(log n). 

How can you formally prove that querying is indeed O(log n), ie the amount of nodes that your algorithm must visit in order to answer any query is in the order of log n?
Querying an interval tree is $O(\log n + m)$, where $n$ is the size of the tree and $m$ is the size of the output. This explains your confusion. Note that there is a trivial $\Omega(m)$ lower bound.

Unfortunately I couldn't find an online proof of this bound, and since there are many variants of interval trees and many different queries, it's best if you tried to prove it yourself for your type of interval tree and query.