GATE CS 2021 Set 1 Q10 — Binary Search Trees

To find any element in a Binary Search Tree (BST) $T$ that is strictly smaller than the maximum element, we can utilize the structural properties of a BST. Assuming $n \ge 2$ (so that such an element always exists):

Let the root of the BST be $R$. We can determine a valid element in $\Theta(1)$ time by checking the right child of $R$:

1. Case 1: $R$ has a right child ($R.\text{right} \neq \text{NULL}$)
   The maximum element of the BST must reside in the right subtree of $R$. Since all elements in the right subtree are strictly greater than $R$, the root $R$ itself is guaranteed to be smaller than the maximum element. Thus, we can simply return $R$.
2. Case 2: $R$ does not have a right child ($R.\text{right} == \text{NULL}$)
   The root $R$ itself is the maximum element of the BST. Since $n \ge 2$, the left child of $R$ must exist. Any element in the left subtree is strictly smaller than $R$ (the maximum). Thus, we can simply return the left child of $R$.

In both cases, we only need to inspect the root and its immediate children. This requires a constant number of operations, resulting in a time complexity of $\Theta(1)$.