recategorized by
2,160 views
1 votes
1 votes
What is the worst case time complexity to construct a binary search tree.???

Now i know ,that if a BST is left or right-skewed, searching an element takes O(n) time.so suppose i want to insert 10,25,30,35,40 in a bst.. it will be completely right skewed..

So when inserting 10 i need 0 comparison, inserting 25 ,i need 1 comparison, insert 30 i need 2 comparison

like that to insert n th node i need (n-1) comparisons

so overall work =0+1+2+...+(n-1)=N(n-1)/2= O(n2)

Am i correct here?? or it is O(nlogn)
recategorized by

1 Answer

0 votes
0 votes
It is ok that it is of O(n^2) in worst case but we can optimise it for every case which takes more time  than the usual one but the order of  time complexity remains same that is O(nlogn).

In this first sort all the elements in O(nlogn).  

Then every time picks the middle element and try to build the binary search tree which takes O(nlogn) time because it become balanced binary search tree.  So total time complexity becomes O(nlogn)+O(nlogn)= O(nlogn).

But when it asked to build the skewed binary search tree the time complexity would become O(n^2).

Related questions

0 votes
0 votes
1 answer
1
0 votes
0 votes
1 answer
2
0 votes
0 votes
1 answer
3