BST creation

Question

what is the time complexity in creating a BInary search tree from an unsorted array??

Answer 1

We can do it in O(nlogn) time.

Step1:->Sort the array.O(nlogn) 

Step2:->Construct Balanced Bst from Sorted array O(n) time.

http://www.geeksforgeeks.org/sorted-array-to-balanced-bst/

So max(step1,step2)= O(nlogn) is ans.

Note:->

1.As here making bst is concern we can always make balanced bst .

2.Here the data is already stored in an array in sorted manner and we are making balanced bst ;So skewed array case will never occur which makes O(n²).

Comments

thanks @sushant and @rajesh..i know its not the best method but i was just confirming the time complexity..

---

For every element of array we start comparing from root and we can go maximum to depth logn
So time should be O(nlogn) ,
as they are specifying unsorted array we should not consider the skewed tree,in that case order will be O(n^2).

---

@Akriti As pointed above the worst case for your code occurs when the input is already sorted in increasing or decreasing order. In that case the complexity of your method is $O(N^2)$.