An array 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 != 0, is A. floor((i-1)/2) B. floor(i/2) C. floor(i/2) - 1 D. floor((i+1)/2) - 1

GATE 2006 · Programming and Data Structures · Binary Tree · medium

Answer: The parent of element X[i] (i != 0) in a 0-indexed complete binary tree array is at index floor((i-1)/2).

1. Derive parent index from left child relationship: If node at index i is a LEFT child of parent at index p, then i = 2p+1. Solving: p = (i-1)/2. For i=1: p = 0. For i=3: p = 1. For i=5: p = 2. All correct.
2. Derive parent index from right child relationship: If node at index i is a RIGHT child of parent at index p, then i = 2p+2. Solving: p = (i-2)/2 = i/2 - 1. For i=2: p = 0. For i=4: p = 1. For i=6: p = 2. Now check floor((i-1)/2): for i=2: floor(1/2)=0. For i=4: floor(3/2)=1. For i=6: floor(5/2)=2. Both cases covered by floor((i-1)/2).