GATE CS 2022 Q18 — Binary Search Trees

In the array representation of a complete binary tree with indices starting at $0$:

• The root is at index $0$.
• For any node at index $i$, its left child is at $2i + 1$ and its right child is at $2i + 2$.

Since the tree is a Binary Search Tree (BST), the largest elements are located along the rightmost path. Let's trace the rightmost path starting from the root:

The next right child would be at index $2(510) + 2 = 1022$. Since the tree has $1000$ elements (indices $0$ to $999$), index $510$ has no right child and is a leaf node.

Now, let's examine the subtree rooted at index $126$ to determine the largest elements in the tree:

• The right child of $126$ is $254$.
• The children of $254$ are $509$ (left child) and $510$ (right child).

By the properties of a BST, for the subtree rooted at $254$:

Since $254$ is the right child of $126$, all elements in the subtree of $254$ are greater than the element at $126$:

Thus, the largest elements in descending order are:

1. 1^st largest: index $510$
2. 2^nd largest: index $254$
3. 3^rd largest: index $509$