Array to Binary Search Trees Quick

Question

Given an array of integers, is there a way to convert it into Binary Search Tree (unbalanced) quickly? I have tried inserting it one by one for each element, but this means that I have to traverse from the beginning for each insertion. It works perfectly, but I think the worst case is O(N^2) for being unbalanced, e.g. the array is sorted. Given a large N, I think it is going to take some time.

Back to my question, is there a way to do this faster than the algorithm that I stated?

For example, given array [4,5,2,3,1], is there a fast way to create this?

    4  
   /  \  
  2    5  
 / \  
1   3

Answer 1

Yes, there is easy way to construct a balanced Binary Search Tree from array of integers in O(nlogn).

Algorithms is as follows:

1. Sort the array of integers. This takes O(nlog(n)) time
2. Construct a BST from sorted array in O(n) time. Just keep making the middle element of array as root and perform this operation recursively on left+right half of array.

---

EDIT:

1. Firstly, you can't do this better than O(nlog(n)) because then you would have essentially sorted the unsorted array (using comparison) in complexity better than O(nlogn). This is impossible.
2. If you don't have to do sorting initially, you could construct binary tree by using binary tree insertion algorithm for each element of the array.

Refer to any standard implementation of Self-balancing BST. While scanning the array, at ith iteration, you have BST for arr[1...i]. Now, you add arr[i+1] to BST (using insertion algorithm).