In a balanced binary search tree with \(n\) elements, what is the worst-case…
2020
In a balanced binary search tree with \(n\) elements, what is the worst-case time complexity of reporting all elements in the range \([a,b]\)? Assume that the number of reported elements is \(k\).
- A.
\(\Theta (\log n)\) - B.
\(\Theta (\log n +k)\) - C.
\(\Theta (k \log n)\) - D.
\(\Theta ( n \log k)\)
Attempted by 389 students.
Show answer & explanation
Correct answer: B
Key insight: locate the start of the range in logarithmic time, then output each reported element in constant amortized time.
Step 1: Search for the smallest element >= a. In a balanced BST this takes Theta(log n) time.
Step 2: From that element, traverse the tree in-order (using successor links or a stack) and report elements until you pass b. Reporting the k elements takes Theta(k) total (amortized O(1) per reported element).
Conclusion: Combining the costs gives Theta(log n + k).