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? DS data-structures binary-search-tree made-easy-test-series + – VS asked Jan 3, 2018 retagged Jul 6, 2022 by Lakshman Bhaiya VS 798 views answer comment Share Follow See 1 comment See all 1 1 comment reply Akash Mittal commented Jan 3, 2018 reply Follow Share inserting keys in this fashion 3, 2, 1, 6, 5, 4, 9, 8, 7, 12, 11, 10, ....., n – 3, n – 4, n – 5, n – 2, n – 1, n you will get a BST with n/3 levels. to search an element in this BST, in worst case O(n) time is required. 4 votes 4 votes Please log in or register to add a comment.
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) Habibkhan answered Jan 3, 2018 selected Dec 24, 2018 by Shaik Masthan Habibkhan comment Share Follow See all 2 Comments See all 2 2 Comments reply prayas commented Jan 11, 2018 reply Follow Share This doesn't make sense.3,6,9 and so on leads to a tree of height n/3.You're presuming we know the arrangement.If that is the case(with array based BST) you could query in O(1). 1 votes 1 votes Aravind Adithya 1 commented Dec 30, 2018 reply Follow Share The question is about BST. Not binary search. In BST if you follow the normal search complexity Is O(n/3) as the tree is right skwed 0 votes 0 votes Please log in or register to add a comment.
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)$. Mr_22B answered Jan 3, 2018 Mr_22B comment Share Follow See 1 comment See all 1 1 comment reply Bunny01 commented Jan 20, 2019 reply Follow Share We can apply Binary search on the root of every right sub tree because they are in sorted sequence. So the answer is O(logn) 0 votes 0 votes Please log in or register to add a comment.