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
The largest element is reached by going right from the root: 0,2,6,…,254,510 (510 has no children since 1021>999). The 2nd largest is its parent 254. The 3rd largest is the rightmost node in 254's left subtree, which is index 509.