GATE 2022 CS Q.28: solution and answer

Official answer: 509Source: Official answer key, GATE 2022 CS (IIT Kharagpur)

1. The array representation of a complete binary tree (root at index 0, children of index $i$ at $2i+1$ and $2i+2$) fixes only the tree's SHAPE. The node values still obey the binary-search-tree property, so ranking by value requires walking the shape with the in-order-predecessor rule, not reading heap order.

2. Locate the largest element: starting at the root (index 0), repeatedly move to the right child ($2i+2$) as long as it exists. This traces $0\to 2\to 6\to 14\to 30\to 62\to 126\to 254\to 510$.

3. Check whether node 510 has any children. With $n=1000$ nodes (valid indices $0$ to $999$): right child $=2(510)+2=1022>999$ (does not exist); left child $=2(510)+1=1021>999$ (does not exist). So index 510 is a leaf and holds the 1st largest (maximum) element.

4. In-order predecessor rule: if a node has no left subtree, its predecessor is its nearest ancestor for which it is a right descendant — here simply its parent. Parent of index $i$ is $\lfloor \frac{i-1}{2}\rfloor$, so the parent of 510 is $\lfloor \frac{510-1}{2}\rfloor =254$. So index 254 holds the 2nd largest element.

5. For the 3rd largest, find the in-order predecessor of node 254. Its left child is $2(254)+1=509$, and $509\le 999$, so this child exists — node 254 DOES have a left subtree.

6. When a node has a left subtree, its predecessor is the maximum (rightmost) element of that subtree, so it is enough to walk as far right as possible starting from node 509.

7. Check node 509's children: right child $=2(509)+2=1020>999$ (does not exist); left child $=2(509)+1=1019>999$ (does not exist). Node 509 is itself a leaf, so it is already the maximum of the subtree rooted at it.

8. Therefore the predecessor of 254 — and hence the 3rd largest element of the tree — is stored at index $\boxed{509}$.