retagged by
798 views
3 votes
3 votes

Consider a Binary Search Tree is created using element 1 to n in following order:

                      3, 2, 1, 6, 5, 4, 9, 8, 7, 12, 11, 10, ....., n – 3, n – 4, n – 5, n – 2, n – 1, n

What is the worst time complexity of searching a number in the Binary Search Tree?

retagged by

2 Answers

Best answer
7 votes
7 votes

Depends on data structure actually . If we use array then we can do binary search on 3 , 6  , 9 and so on till n and which is a multiple of 3 ..  Having got a suitable multiple we can then descend towards left searching for the key under the root which is a multiple of 3..

So time taken to find closest multiple of 3 = O(logn)

And to descend to get key = O(1) .. [ At most 3 comparisons , say under root '3' , we have '2' and '1' , hence to descend to '1' and hence search for it we need 3 comparisons ]..

Hence overall complexity considering this scenario = O(logn) 

selected by
1 votes
1 votes

I request you to draw Binary Search Tree for at least 15 Nodes to verify my answer.

If you will draw Binary search tree then you will get 

Height = $\left [ \frac{N}{3} + 1 \right ]$

so its obvious that in the Worst case $O(N)$ comparison take place.

Hence, Final answer  $O(N)$.

Related questions

0 votes
0 votes
1 answer
1
aditi19 asked Oct 1, 2018
598 views
what are the applications of optimal binary search tree?
1 votes
1 votes
0 answers
2
Anjan asked Jan 9, 2018
325 views
Find number of BST's possible with 6 nodes numbered 1,2,3,4,5 and 6 having 6 as root and height of 4 ?please explain in detail ...
1 votes
1 votes
2 answers
3
rajoramanoj asked Nov 6, 2017
835 views
1 votes
1 votes
0 answers
4
srestha asked Oct 31, 2017
414 views
The number of BST possible with 6 nodes numbered 1,2,3,4,5,6 with exactly 1 leaf node __________