Project ForgeData Structures
Trees
GATE 2020
Medium
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.
- AΘ(log n)
- Θ(log n + k)
- CΘ(k log n)
- DΘ(n log k)
Explanation
A balanced-BST range query first descends to the 'split node' where the search paths for a and b diverge — this costs O(log n) — and then walks along the boundary of the subtree(s) covering [a,b] to output each of the k qualifying elements in O(1) amortized time per element. Total cost = O(log n) for the search plus O(k) for reporting = Θ(log n + k).
Source: GATE CS 2020 (2020)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.