Algorithms
October 12, 2023AsymptoticComplexity
October 12, 2023Algorithms
Question 25

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_____________.
509

Question 25 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
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 25 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
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
Subscribe
Login
0 Comments