The GATE Grind

GATE 2020 CS – Question 51

Programming and Data Structures · Trees and Binary Search Trees · 2 marks · Multiple choice

In a balanced binary search tree with $n$ elements, what is the worst case time complexity of reporting all elements in range $[a,b]$? Assume that the number of reported elements is $k$.

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

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) $\Theta(\log n+k)$

Explanation

Locating $a$ and $b$ takes $O(\log n)$, and an in-order traversal of the reported elements takes $O(k)$. Total $\Theta(\log n+k)$.