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_____________.
Correct Answer:
509
Solution:
In a complete binary tree with 1000 elements, the number of levels is log2(1000) ≈ 10. As the given binary tree is a binary search tree the largest element should be the rightmost element in the right subtree.
As the tree is stored using array representation of binary heap trees. So the 3rd largest element index is 509.