Understanding construction from an unsorted array

Constructing a binary search tree from an unsorted array of values is easy. It is not always the best method, but it is one of the easiest. 

Algorithm

To construct a binary search tree from a given sequence, we start with an empty binary tree and insert all the elements in the sequence into it individually.

Algorithm

• Step 1: Initialize the `root` of the BST as `null` (empty tree).
• Step 2: Iterate through the elements of the input array, do the following:
  • Step 2.1: Insert the `current` element into the BST rooted at `root`.
• Step 3: Return the `root` of the BST, representing the `root` of the constructed BST.

Implementation

The implementation of the algorithm is quite straightforward. We implement an insert function that inserts a value into the given tree and repeatedly calls it for all the elements in the sequence.

Complexity Analysis

The algorithm for constructing a binary search tree by inserting values sequentially into an empty tree involves traversing the entire sequence once, which has a linear time complexity. However, we also insert a BST for every element in the sequence. Insertion in a BST has a best-case time complexity of O(log(N)) and a worst-case time complexity of O(N). Let's understand better what the best and the worst cases are.

Best Case

The best cases will be when every insert in the binary search tree takes O(logN) time. This can only happen if the tree is height-balanced at every step in the interaction. Let us look at an example of such a case.

Observing the example case above and extrapolating it, we hit the best case when the given sequence represents the level order traversal of a height balanced binary search tree. In such cases, the constructed tree will remain height balanced at all points in the iteration so that every operation will take O(logN) time. Since this operation is repeated for all elements in the sequence, the overall runtime complexity will be O(NlogN).

Worst Case

The worst case is when every insert operation in the binary search tree takes O(N) time. This will happen when the tree being constructed is skewed at every point.

We observed the example case and extrapolated it further. When the given sequence is sorted, we hit the worst case. In such cases, the tree constructed will be a skewed tree at all points in the iteration, so the insertion will always take O(N) time. Since this operation is repeated for all elements in the sequence, the overall runtime complexity will be O(N*N) = O(N2).

Since this algorithm also creates an entirely new tree, the space complexity, in any case, is linear O(N).

Best Case : The input sequence is the level order traversal sequence of balanced binary search tree.

• Space Complexity - O(N)
• Time Complexity - O(N(log(N))

Worst Case : The input sequence is sorted

• Space Complexity - O(N)
• Time Complexity - O(N^2)