Question 28

The tree has 1000 nodes indexed $0$ to $999$ in array representation, where for node $i$, its left child is $2i+1$ and right child is $2i+2$.

In a complete binary tree with 1000 nodes:

• The first 9 levels (level 0 to 8) are completely full, containing $\sum_{k=0}^8 2^k = 2^9 - 1 = 511$ nodes, spanning indices $0$ to $510$.
• Level 9 contains the remaining $1000 - 511 = 489$ nodes, occupying indices $511$ to $999$.

Since the tree is also a Binary Search Tree (BST), the in-order traversal visits nodes in strictly increasing sorted order.

• Node 510 has children at $2(510)+1 = 1021$ and $2(510)+2 = 1022$, which are both $> 999$, so 510 is a leaf.
• The parent of node 510 is $\lfloor(510-1)/2\rfloor = 254$. Node 510 is the right child of node 254 ($2 \times 254 + 2 = 510$).
• The left child of node 254 is $2 \times 254 + 1 = 509$. Node 509 has children at $2(509)+1 = 1019 > 999$ and $2(509)+2 = 1020 > 999$, so 509 is also a leaf.

Now observe the rightmost portion of the BST:

• Node 254 has no ancestors to its right because $254$ is the right child of $126$, which is the right child of $62$, and so on up to the root.
• Therefore, the subtree rooted at node 254 contains the largest elements of the entire BST.
• In the subtree at node 254, the in-order traversal visits: left child (node 509), root (node 254), right child (node 510).
• Thus, the 3 largest elements of the tree in increasing order are: node 509 (3rd largest), node 254 (2nd largest), and node 510 (1st largest).

Hence, the 3rd largest element is stored at index 509.