edited by
13,533 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$. The index of the parent of element $X[i], i \neq 0$, is?

  1. $\left \lfloor \dfrac i 2 \right \rfloor$
     
  2. $\left \lceil \dfrac{i-1}{2} \right \rceil$
     
  3. $\left \lceil \dfrac i 2 \right \rceil$
     
  4. $\left \lceil \dfrac i 2 \right \rceil - 1$
edited by

5 Answers

Best answer
46 votes
46 votes

Option is (D).

Left child of ith element will be at $2*i+1$ and right child at $2(i+1)$

5 votes
5 votes

$Ans: D$


The value inside the node is array index

Parent of $4: \left \lceil \dfrac{i}{2} \right \rceil-1=>2-1=>1$

Parent of $3: \left \lceil \dfrac{i}{2} \right \rceil-1=>2-1=>1$

Parent of $2: \left \lceil \dfrac{i}{2} \right \rceil-1=>1-1=>0$

Parent of $1: \left \lceil \dfrac{i}{2} \right \rceil-1=>1-1=>0$

1 votes
1 votes
D is the correct answer
edited by
1 votes
1 votes
how is this working in the case of indexing start from the 2 and if i have checked that this is working fine with the indexing starting from the o and 1 but this is not genral i hope so .
 and in case of o and 1 more formulas are also there
 ceil ((i-2)/2) and floor ((i-1)/2) (in the cases of indexing from the 0 and in case of indexing from 1 subtract 1 from the result of both)
please correct me if i am wrong.
Answer:

Related questions

57 votes
57 votes
11 answers
2
Ishrat Jahan asked Oct 31, 2014
25,889 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...