in DS retagged by
3,860 views
9 votes
9 votes
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 $3^{\text{rd}}$ largest element of the tree is stored at index ______________ .
in DS retagged by
by
3.9k views

2 Answers

15 votes
15 votes
Best answer

Answer $509$

For 1000 elements, there will be 10 levels (root is at level 1). But last level will not be completely filled since there are only 1000 elements.

 

As you can see, some portion is empty. Since largest element can not have children as there are not enough nodes. – we need 1023 nodes to fill all levels.

Now lets see if $A$ in below diagram has children ?

Again, we do not have enough nodes that’s why A will not be having subtree.

Now,

largest will be at rightmost of 9th level, (Easy to see…..just keep going right)
2nd largest will at rightmost of 8th  level, (because if you want to find larger than this then you need to go on right side and there is just one element on right side)

Where will be $3^{rd}$ largest ?

Since we know that inorder of BST is sorted hence 3rd largest will be a element just before 2nd largest in inorder. What we call such element ? – inorder predecessor. 

Hence 3rd largest will be inorder predecessor of 2nd largest. – which is $A$ in above diagram.

Lets find index of 2nd largest then we can find index of 3rd largest.

index of 2nd largest. (Assuming index starts from 1)

$1 \rightarrow 3 \rightarrow 7 \rightarrow 15 \rightarrow 31 \rightarrow 63 \rightarrow 127 \rightarrow 255$

Index of 3rd largest = $510$

Since indices are starting from 0 hence answer is $509$

edited by

2 Comments

Sir isn’t the third largest will be a sibling of the 9th level index?

1
1
Thank you Sir... What an explanation 💯
0
0
6 votes
6 votes

Answer is 509 

we will see by doing analysis on small no of elements 

Answer:

Related questions