Question 20

Let the root of the binary search tree $T$ be $r$. By definition of a BST, all keys in the left subtree of any node $u$ are strictly smaller than $u$, and all keys in the right subtree are strictly greater than $u$.

Consider the root $r$ of $T$ (with $n \ge 2$ distinct elements):

1. If $r$ has a right child ($r.\text{right} \neq \text{NULL}$), then the maximum element of $T$ resides somewhere in the right subtree of $r$. Hence, $r$ is strictly smaller than the maximum element! We can simply return $r$.
2. If $r$ has no right child ($r.\text{right} == \text{NULL}$), then $r$ itself is the maximum element of $T$. Because $n \ge 2$, $r$ must have a non-empty left subtree. Any node in this left subtree is smaller than $r$. In particular, the left child $r.\text{left}$ is strictly smaller than $r$ (the maximum element)! We can simply return $r.\text{left}$.

In either case, we inspect only the root and its child pointers. No tree traversal or search is needed, taking $\Theta(1)$ constant time (option D).