GATE CS 2020 Q.51 (CS Q.41): Binary Trees, Binary Search Trees and Balanced Trees

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

$O(\log n)$

$O(\log n + k)$

$O(k \log n)$

$O(n \log k)$

Official answer and solution

Official answer: B
From: Official GATE 2020 answer key

Solution

Analyze the search phase to locate the lower bound and the subsequent inorder traversal phase.

Phase 1: Locating the start of the range:

In a balanced binary search tree of $n$ elements (such as an AVL tree or Red-Black tree), tree height is $\Theta(\log n)$ .
Searching for the smallest key $\ge a$ takes $O(\log n)$ time.

Phase 2: Reporting the $k$ elements in range $[a, b]$ :

From the first key $\ge a$ , an inorder traversal continues visiting nodes until encountering a key $> b$ .
In an inorder traversal of a binary search tree, the amortized cost to find each successor node is $O(1)$ .
Traversing and outputting the $k$ elements within the range, plus reaching the first element $> b$ , takes $O(k)$ time.

Total worst-case time complexity:

O(\log n) + O(k) = O(\log n + k)

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2020 Computer Science and Information Technology (CS)
Question: 51 of 65, printed as CS Q.41
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source