An array X of n distinct integers is interpreted as a complete binary tree. If…
2006
An array X of n distinct integers is interpreted as a complete binary tree. If the first array index is 0, what is the parent index of element X[i] for i ≠ 0?
- A.
⌊i / 2⌋
- B.
⌈(i - 1) / 2⌉
- C.
⌈i / 2⌉
- D.
⌈i / 2⌉ - 1
Attempted by 350 students.
Show answer & explanation
Correct answer: D
Correct answer: ⌈i / 2⌉ - 1
For a complete binary tree stored in a 0-based array, the children of index p are at 2p + 1 and 2p + 2.
Solving backwards gives the parent of index i as ⌊(i - 1) / 2⌋.
For integer i, ⌊(i - 1) / 2⌋ = ⌈i / 2⌉ - 1.
Examples: i = 1 → 0, i = 2 → 0, i = 3 → 1.