What is the level number of an element present in an array of n integers interpreted as a complete binary tree?

Question

If I am given an array $X$ of $n$ distinct integers which is interpreted as a complete binary tree, so if the parent is at index $i$, then it's left child would be at index $2i$ and it's right child would be at index $2i+1$. If root is considered to be at level $0$, then how can we find the level of an element $X[i]$?

I followed the approach of first considering the fact that at a level $k$, I would be having $2^k$ nodes. So I just considered that in the array starting from certain index $a$ up to $b$, I have all the numbers at the same level $k$. That is, in a particular portion I have $2^k$ nodes inclusive of $a$ and $b$.

Thus, before $a$ the total no of nodes is $2^0+2^1+2^2+ \dots +2^{k-1}$, since index $a$ is at level $k$, and before it there would be $k-1$ levels.

Now I am stuck while calculating the value of $b$.

Please guide about how to calculate the value of $b$?

Answer 1

Simply take the $\log$! So,

$$\text{level } = \left \lfloor \log_2{(\text{index})} \right \rfloor$$

• The root (index$=1$) is at level $\log_2 1 = 0$
• The elements at index $2, 3$ are both at level $\left \lfloor \log_2{2} \right \rfloor = \left \lfloor \log_2{3} \right \rfloor = 1$
• The elements at index $4,5,6,7$ are all at level $\left \lfloor \log_2{4} \right \rfloor = \left \lfloor \log_2{5} \right \rfloor = \left \lfloor \log_2{6} \right \rfloor = \left \lfloor \log_2{7} \right \rfloor = 2$
• And so on.

---

If you wish to continue with your approach:

Let both $a$ and $b$ be at the level $k$.

Number of nodes before $a$ can be given as: $2^0 + 2^1 + 2^2 + \dots + 2^{k-1}$. This huge sum is just the sum of a Geometric Progression, and is equal to $2^k - 1$.

So, $a$, the first element at level $k$ is infact the $2^k$th element of the tree! (This is a nice property of complete trees)

Since $b$ is the last element of level $k$, the index of $b$ is simply $2^{k+1}-1$.

Now, let us assume that the element $X[i]$ is on the level $L$.

Since the indices of the first and last elements on the level $L$ are $2^L$ and $\left (2^{L+1}-1 \right )$ respectively, we know that $i$ must be within that range. So, $$2^L \quad \leq \quad i \quad \leq \quad 2^{L+1}-1$$

Taking $\log_2$, we get: $$L \quad \leq \quad \log_2{i} \quad \leq \quad L+1 - \varepsilon$$

$\varepsilon$ is a small error which was introduced when we ignored the $-1$ while taking $\log$ of $2^{L+1}-1$

So, we have: $$L = \left \lfloor \log_2 i \right \rfloor$$

Comments

umm.. no. We are taking the floor of the log of the index.

For example, $\log_2(5) \approx 2.3219$.

Since the level can't be a fraction, we take the floor of it to get $2$. And infact, the level of the $5^{th}$ element will be $2$.

---

Yes ,thats true since it will be a fraction so we will either take floor or take ceil so you chose floor that is why I said that we must be considering the maximum level at which that index must be present .

---

You can look at it in one more way.

$$L \quad \leq \quad \log_2{i} \quad \color{red}{\leq} \quad L+1 \;\color{red}{- \varepsilon}$$

As we can see, $\log_2 i$ is greater than or equal to L.

But since there is a $-\varepsilon$ along with the $L+1$, we have that $\log_2 i$ is strictly smaller than $L+1$ (that is, $<$ and not $\leq$)

So, we can write: $L \leq \log_2 i \color{red}{<} L+1$

This means that $\lfloor \log_2 i \rfloor = L$

Answer 2

Since for an index i you can visit its parent by Floor(i/2).

So go recursively upwards till u reach  root. So max complexity of finding level of a particular index node O(logN) if N is no of element in tree.

Answer 3

the value of b is a+2^k  but this is not the best  way to find out the level of a node.

Answer 4

as u stated that the left child at 2i array is starting at 1.

so simply take floor(log i) where i is the index.