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.
Θ(log n)
B.
Θ(log n + k)
C.
Θ(k log n)
D.
Θ(n log k)
Solution:
In Balanced BST worst-case time taken to find a and b will take O(log n).
To traverse all k elements within the range [a, b] will take extra O(k) time in the worst case.
So, the overall time complexity = Ο(log n + k).