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

Dark Mode

3,860 views

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 ______________ .

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 2^{nd} largest then we can find index of 3^{rd} largest.

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

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

Index of 3^{rd} largest = $510$

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