A binary search tree \(T\) contains \( n\) distinct elements. What is the time…

Answer: θ(1)

Reasoning (assume n ≥ 2):

• Key insight: a constant-time check at the root suffices.

• If the root has a right child, then the maximum lies in the root's right subtree, so the root's key is smaller than the maximum. Return the root immediately in O(1).

• If the root does not have a right child, then the root is the maximum. Since n ≥ 2, the root must have a left child; any node in that left subtree (for example, the left child) is smaller than the maximum. Return the left child in O(1).

• If n = 1, no element smaller than the maximum exists; the problem is trivial in that case.

Because the required checks and the returned node are found without traversal, the operation runs in constant time, θ(1).