The GATE Grind

GATE 2021 CS – Question 20

Programming and Data Structures · Trees and Binary Search Trees · 1 mark · Multiple choice

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

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (D) $\Theta(1)$

Explanation

Take the root. If it is not the maximum, it qualifies. Otherwise it has no right child, so its left child (or any left-subtree element) is smaller. This takes constant time.