5,200 views
7 votes
7 votes

What would be the worst case time complexity to build binary search tree with given arbitrary n elements?

A) O(nlogn)

B) O(n)

C) O(n^{2})

D) O(log n)

3 Answers

Best answer
5 votes
5 votes
#Edited

Copied from @vijaycs correct comment

[I was initially wrong]

Here we are asked to build binary search tree with n arbitrary elements but it is not mentioned in the question that we have to insert elements in incoming order.

So, what we can do here is - first sort the n elements and then insert elements in BST by choosing middle element as root of BST and all elements less than middle should go in left of root and greater than middle should go in right of root.

DO the same for left of root and right of root.

I think it will do the job in O(nlog n).
selected by
5 votes
5 votes
You have to make binary search tree of keys 10, 9, 8, 7, 6, 5, 4, 3, 2,1

It will be O($n^2$) since skew bst will be work as insersion sort .
For 1st element no comparision

For 2nd element 1 comparision

For 3rd element 2 comparision

.......

total comparision : 1+2+3+4+5+6...n-1 = O($n^2$)
0 votes
0 votes

If Binary Search Tree (BST) is not perfectly balanced, then the worst case time complexity is O(n^2). If build by repeated insertion, so worst case will be O(n^2) instead if you can sort the input (in O(nlogn)), it can be built in O(n), resulting in overall complexity of O(nlogn)

If BST is self-balancing, then the worst case time complexity is O(nlog n) even if we have repeated insertion

Related questions

0 votes
0 votes
1 answer
1
1 votes
1 votes
1 answer
2
rahul sharma 5 asked Apr 12, 2018
667 views
a:) If given Tree is BST = Inorder of keys is sortedb:) Inorder of keys is sorted = Tree is BST(converse of above)I know first one holds.Is second one also true?If not ca...
1 votes
1 votes
2 answers
3
rahul sharma 5 asked Oct 6, 2017
782 views
What is the time complexity to delete the root node in right skew tree?I knew the three cases of BST deletion:- 0 child,one child,two child.But how can we handle this par...
2 votes
2 votes
1 answer
4
rahul sharma 5 asked Oct 2, 2017
445 views
What is the worst case time complexity to construct unique BST froma:) Inorder and preordera:) Inorder and postorder