Understanding construction from a sorted array

We know that the inorder traversal of a binary search tree generates a sorted sequence. However, reconstructing a height-balanced binary search tree from this sorted sequence is also possible. This is only true for a binary search tree because of its special properties.

Resolving ambiguity

Using just the inorder traversal sequence to reconstruct a generic binary tree is impossible. We cannot identify the root by looking at the inorder traversal sequence. This ambiguity is generally resolved by using either the preorder or postorder traversal sequence in tandem with the inorder sequence, as for them, the position of the root is always at the beginning or the end, respectively. 

This means that for reconstructing a binary tree from the inorder traversal sequence, the other sequence(preorder or postorder) is just used to identify the location of the root node for every subtree.

What if there was another way to resolve this ambiguity without using the second traversal sequence(pre or postorder)? In the case of a binary search tree, this can be done by imposing the condition of height balance on the constructed tree. By imposing this condition, we can effectively resolve the ambiguity in root selection, as we will see shortly.

Construction

To construct a height balanced binary search tree from a sorted array, we follow a simple idea. For a binary tree to be height balanced, every node in the tree should typically have a similar number of nodes in its left and right subtrees. To ensure this happens, we make the value at the middle of the sorted array the root of the binary tree.

All the values to the left of this value will make up the root's left subtree, and all the values to the right make up the right subtree. This way, both the left and right subtree of the root will have a similar number of nodes. We construct the left and the right subtree in the same way by applying the same logic recursively. As evident from above, imposing the condition of height balance effectively resolves the ambiguity in selecting the root node for every subtree.

Algorithm

We can implement the idea by piggybacking on any of the recursive tree traversal algorithms and constructing the tree along the way. In the algorithm below, we use the preorder traversal algorithm, where we first construct the root node, followed by its left and right subtrees. However, at every point in traversal, we need to know exactly where the subtree rooted at the current node lies in the given sorted array. To accomplish this, we use two pointers st and en to keep track of the range in the array that holds the current subtree. To understand the algorithm better, let's look at the following example.

We can summarise the algorithm as the following recursive equation.

Algorithm

• Step 1: If the `start` index is greater than the `end` index, there are no elements in this subarray. In this case, return `null` to indicate an empty subtree (base case).
• Step 2: Calculate the `middle` index of the current subarray.
• Step 3: Create a new node with the element's value at the array's `middle` index.
• Step 4: Recursively build this new node's `left` subtree using the elements to the left of the `middle` index.
• Step 5: Recursively build this new node's `right` subtree using the elements to the right of the `middle` index.
• Step 6: Return the new node at the end of recursion.

Implementation

A simple recursive function can implement the algorithm in a few lines.

Complexity Analysis

The algorithm constructing a balanced binary search tree from a sorted array is just some extra logic on top of recursive preorder traversal. So, the runtime complexity is linear, just like traversal. The space complexity is linear since we also construct an entire tree.

Best Case

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

Worst Case

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