GATE 2022 CS – Question 28
Suppose a binary search tree with 1000 distinct elements is also a complete binary tree. The tree is stored using the array representation of binary heap trees. Assuming that the array indices start with 0, the 3rd largest element of the tree is stored at index _____________.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 509
Explanation
A complete binary tree stored in an array with indices starting at 0 has children of node $i$ at $2i+1$ and $2i+2$. With 1000 nodes, indices $0,\dots,999$ exist.
Because the tree is also a BST, larger keys are further right.
1. **Largest element:** follow right children from the root: $0\to2\to6\to14\to30\to62\to126\to254\to510$. The next right child would be $2\cdot510+2=1022>999$, so 510 is the last node on the spine and holds the **largest** key. Node 510 has no children (its left child would be 1021), so nothing is larger or smaller below it.
2. **2nd largest:** the predecessor of the maximum. Node 510 has no left subtree, so the predecessor is the ancestor from which we last turned right: node **254**.
3. **3rd largest:** the predecessor of 254 is the **largest key in 254's left subtree**. The left child of 254 is $2\cdot254+1=509$, which has no right child ($2\cdot509+2=1020>999$). So the maximum of that subtree is 509 itself.
The 3rd largest element is at index **509**.