1,082 views

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$?

1. $\Theta(n\log n)$
2. $\Theta(n)$
3. $\Theta(\log n)$
4. $\Theta (1)$