edited by
8,881 views
44 votes
44 votes

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

  1. $\left \lfloor \log _2 i \right \rfloor$ 
  2. $\left \lceil \log _2 (i+1)\right \rceil$
  3. $\left \lfloor \log _2 (i+1) \right \rfloor$ 
  4. $\left \lceil \log _2 i \right \rceil$
edited by

3 Answers

Best answer
33 votes
33 votes

PS : the value inside the node is array index

  1. FALSE , $\left \lfloor \log _2 i \right \rfloor = \left \lfloor \log _2 1 \right \rfloor  = 0 $ but $X[1]$ is at level $1$
  2. 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$
  3. Correct
  4. FALSE , $\left \lceil \log _2 i \right \rceil = \left \lceil \log _2 1 \right \rceil  = 0 $ but $X[1]$ is at level $1$
edited by
23 votes
23 votes
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
Answer:

Related questions

57 votes
57 votes
11 answers
2
Ishrat Jahan asked Oct 31, 2014
25,856 views
In a binary tree, the number of internal nodes of degree $1$ is $5$, and the number of internal nodes of degree $2$ is $10$. The number of leaf nodes in the binary tree i...