GATE CSE 2020 | Question: 41

Question

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. $\Theta (\log n)$
• B. $\Theta (\log n +k)$
• C. $\Theta (k \log n)$
• D. $\Theta ( n \log k)$

Comments

@Nagasaikanmatha When asked for worst case, generally option elimination is not good. It is always important to actually determine the worst case and then mark the correct option. Option elimination is useful if asked for the “most efficient algorithm.”

---

same question like 2014 L and H question

---

 For Visualization :-

 

it is pic of answer given by https://gateoverflow.in/user/Shikhar. 

Answer 1

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

Comments

Can you please confirm, if the logic of my solution is correct?

---

@Yashdeep2000 your time complexity for statement 1 is wrong because you are traversing the balanced BST which takes O(n) time . 

---

Search for a in BST = O(log n)

Search for b  = O(log n)

And finally print K elements in between  = O(k)

Total = k + O(log n)

Answer 2

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)

Comments

agreed brother

---

We cannot print k, as we don’t know for sure that all elements in the range (a+1..b-1) ar present in the bst. One of the counter example might be a, a+1, a+3, a+6, a+10...b

---

what if neither of the elements in the range [a,b] is present in the given BST? It will be the worst case, isn't it?

Answer 3

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

Comments

@mkagenius

Then , is TIFR question ans wrong? It is telling only logn comparison and logn addition?

logn addition means T.C. also log n ,right?

---

No more answers, please complete the above exercise first. I want you to figure your own questions yourselves, otherwise its of no use.

---

which one?program?

Answer 4

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)