Question

A binary search tree \( T \) contains \( n \) distinct elements. What is the time complexity of picking an element in \( T \) that is smaller than the maximum element in \( T \)?

• A. \( \Theta(n \log n) \)
• B. \( \Theta(n) \)
• C. \( \Theta(\log n) \)
• D. \( \Theta(1) \)

Hint:

If a problem only requires selecting any valid element and not searching for a specific one, the operation can often be done in constant time.

Answer 1

The Correct Option is D

Step 1: Understand the requirement.
The task is to determine the time required to pick any element from a Binary Search Tree (BST) that is smaller than the maximum element.

---

Step 2: Key observation about a BST.
In a BST with distinct elements, the maximum element is always located at the rightmost node.

Every other node in the tree is strictly smaller than this maximum element.

---

Step 3: Time complexity analysis.
We do not need to search for the maximum or traverse the tree.

We can simply select the root (or any known node that is not the maximum), which immediately satisfies the condition.

This selection requires no traversal or comparisons and hence takes constant time.

---

Final Conclusion:
The time required to pick an element smaller than the maximum in a BST is:

Θ(1)