GATE IT 2006 | Question: 71

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

• A. $\left \lfloor \dfrac i 2 \right \rfloor$
   
• B. $\left \lceil \dfrac{i-1}{2} \right \rceil$
   
• C. $\left \lceil \dfrac i 2 \right \rceil$
   
• D. $\left \lceil \dfrac i 2 \right \rceil - 1$

Comments

can somebody explain the actual method of storing CBT in array? other than substitution.

---

found this on YT – https://www.youtube.com/watch?v=fJORlbOGm9Y&ab_channel=PaulProgramming

---

Derivation here

Answer 1

Option is (D).

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

Comments

Option B is using a ceil function which is giving wrong answers !

Use a floor function instead of ceil then it would give the correct result as option D ... Think about it and try it on a example !

---

@vaishnavi30 For bigger example difference is visible.

let i = 20

option B) $\left \lceil (20-1)/2 \right \rceil = \left \lceil 9.5 \right \rceil = 10$

option D) $ \left \lceil 20/2 \right \rceil -1 = 10 -1 = 9$

---

you need to be careful with the notations in this question:

• ⌈ ⌉ means Ceil

• ⌊ ⌋ means Floor

Initially, I thought Option B was correct because I mistook it for a floor expression. But since it actually uses ceil, Option B is wrong. That’s why the only correct answer is Option D.

Answer 2

$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$

Comments

suppose index (i) start from 2, then parent of ith node will be  ceil(i/2).

Is it correct?

---

If we follow this method ,then option B also correct floor(i-1/2)

As per diagram,

Parent of 4=(i-1/2)=(4-1)/2=1

parent of 3=(i-1/2)=(3-1)/2=1

parent of 2=(i-1/2)=(2-1)/2=0

parent of 1=(i-1/2)=(1-1)/2=0

Answer 3

see this

Answer 4

If index of array start with 1 then directly divide the ith value by 2 and take floor..if index start with 0 then ceil(i/2)-1 .

Comments

suppose index (i) start from 2, then parent of ith node will be  ceil(i/2).

Is it correct?

Answer 5

D is the correct answer

Comments

B & D is not same. Try on bigger example.

---

yes.you are correct.but options has been changed, previously (B) option was ⌈(i-2)/2⌉.that's why i said b and d are same.

Answer 6

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.