GATE IT 2006 | Question: 73

Question

An array $X$ of n distinct integers is interpreted as a complete binary tree. The index of the first element of the array is $0$. If the root node is at level $0$, the level of element $X[i]$, $i \neq 0$, is

• A. $\left \lfloor \log _2 i \right \rfloor$ 
• B. $\left \lceil \log _2 (i+1)\right \rceil$
• C. $\left \lfloor \log _2 (i+1) \right \rfloor$ 
• D. $\left \lceil \log _2 i \right \rceil$

Comments

root node is always at Level 1.How level 0 come at root ?

---

Can any one explain the concept of flooring?

---

@Chawlaajay Just take the lower integer value.

for example floor of 4.4 is 4. (Since, we have to take the lower integer value).

Similarly, floor of -4.4 is -5. (Since, -5 is smaller than -4)

Answer 1

PS : the value inside the node is array index

• A. FALSE , $\left \lfloor \log _2 i \right \rfloor = \left \lfloor \log _2 1 \right \rfloor  = 0 $ but $X[1]$ is at level $1$
• B. FALSE ,  $\left \lceil \log _2 (i+1) \right \rceil = \left \lceil \log _2 (4+1) \right \rceil = \left \lceil \log _2 (5)\right \rceil = 3 $ but $X[4]$ is at level $2$
• C. Correct
• D. FALSE , $\left \lceil \log _2 i \right \rceil = \left \lceil \log _2 1 \right \rceil  = 0 $ but $X[1]$ is at level $1$

Comments

You have to use the definition of complete binary tree based on the context. A heap is a complete binary tree or almost complete binary tree?

---

Okay sir, got it. Heap is a almost complete binary tree as per CLRS but in some other text it’s considered complete binary tree. I understood what you are trying to imply.

---

On above grounds can https://gateoverflow.in/663/Gate-cse-2000-question-2-16: question be considered ambiguous? Since on basis of definition we can have B or D as answers. Which one should we consider in such cases as per your opinion.

Answer 2

Hope it helps.

Comments

Nice Explanation

---

nice ans.

---

Fill the secold last level $+$One node at last level  $\leq$ Total nodes in Complete Binary Tree

$(2^0+2^1+....+2^{l-1})+1\leq(i+1)$ [As index starts from $0$]

$\implies2^{l}-1+1\leq i+1 \implies l\leq log_2(i+1)$

Answer 3

Floor(log(i+1)) draw the tree and realise that the last element at each level is the best choice to arrive at a conclusion

Comments

C is ans

---

why not option d)? Please explain

---

for index 1 it wil give 0 level which is not correct