retagged by
21,505 views
29 votes
29 votes

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)$
retagged by

4 Answers

Best answer
43 votes
43 votes
First, you'll have to check if the elements $a$ and $b$ are present in the BST or not. Since the BST is balanced, it will take $\Theta(\log_2(n))$ time for that. Traversing the $k$ elements would take additional $\Theta(k)$ time.

Hence $\Theta(\log_2(n) + k)$
edited by
11 votes
11 votes

We need to first find the indices of a & b, which takes time of log n + log n (Since it is Balanced BST). Once we find the indices, we can directly print the k elements.

As k can be significantly larger than log n, time complexity is O(log n + k)

1 votes
1 votes
The question asks about worst case time complexity. The worst case can be achieved by implementing the BST using singly linked list. and here it will take log(N) time complexity as the tree is balanced and for k numbers the time complexity becomes O(kLogN). This is what was in my mind while attempting the question in the exam hall.   

Option (C).
0 votes
0 votes

For checking the Reporting element is in range you will do checking of 2 nodes at each height .

And Between the you can have “k” nodes which will encounter in the counting range . 

So total element ( node ) for reporting all element in range [a,b] will be : ( k + 2*h) where k: nodes in the range , 2*h : Total  Number of nodes which you will check at each height .

Height ( h) = logn     ( BST ) 

So, worst overall complexity  Ɵ(k+2*logn) 

 

Answer:

Related questions

8 votes
8 votes
5 answers
1
Arjun asked Feb 12, 2020
18,577 views
The preorder traversal of a binary search tree is $15, 10, 12, 11, 20, 18, 16, 19$. Which one of the following is the postorder traversal of the tree?$10,11,12,15,16,18,1...
28 votes
28 votes
6 answers
2
Arjun asked Feb 12, 2020
14,742 views
Consider the array representation of a binary min-heap containing $1023$ elements. The minimum number of comparisons required to find the maximum in the heap is _________...
2 votes
2 votes
2 answers
3
go_editor asked Jul 24, 2016
4,720 views
Given a binary search trees for a set of $n=5$ keys with the following probabilities $:$$\begin{array}{|l|l|l|l|l|l|l|}\hline \text{i} & \text{0} & \text{1} & \text{2} &...