...
Hashing
October 12, 2023
Asymptotic-Complexity
October 12, 2023
Hashing
October 12, 2023
Asymptotic-Complexity
October 12, 2023

Binary-search-tree

Question 8
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_____________.
A
509
Question 8 Explanation: 
Array indices shown beside node

Now, the 3^rd largest number will be at location of max3. We can find what can be the probable index values of max1 at different levels. They will be 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023 . . .
∴ 511 is index value of our max1
510 is index value of our max2
509 is index value of our max3
& Hence, Answer is 509
Correct Answer: A
Question 8 Explanation: 
Array indices shown beside node

Now, the 3^rd largest number will be at location of max3. We can find what can be the probable index values of max1 at different levels. They will be 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023 . . .
∴ 511 is index value of our max1
510 is index value of our max2
509 is index value of our max3
& Hence, Answer is 509

Leave a Reply

Your email address will not be published. Required fields are marked *