Solution: Convert Sorted Array to Binary Search Tree

Statement

Given an array of integers, nums, sorted in ascending order, your task is to construct a height-balanced binary search tree (BST) from this array.

In a height-balanced BST, the difference of heights of the left subtree and right subtree of any node is not more than 1.

Note: There can be multiple valid BSTs for a given input.

Constraints:

• $1 \leq$ nums.length $\leq 10^3$
• $-10^4 \leq$ nums[i] $\leq 10^4$
• nums is sorted in strictly ascending order.

Solution

Let’s use a sorted array of three elements to explain the solution. In this array, the first element is smaller than the middle element, and the third element is greater than the middle element. Therefore, we can use the middle element as the root, the first element as the left child, and the third element as the root’s right child. This approach ensures a balanced binary search tree (BST). To create the BST from a larger sorted array, we recursively apply the same process: select the middle element as the root, then use the left half of the array to construct the left subtree and the right half for the right subtree. To do so, calculate the middle element from the left subarray, and make it the left node of the root. Similarly, calculate the middle element from the right subarray, and make it the right node of the root. Continue dividing the array and constructing subtrees until all elements are placed in the tree. Repeating this process ensures the tree is balanced and the left and right subtrees have minimal height differences.

Here are the implementation details of the above algorithm:

Create a recursive function that takes an array, nums, along with the first, low index and the last, high index. The steps of the recursive function are given below:

1. The base case is low > high, meaning no more elements remain to add to the tree. Therefore, return NULL.
2. If the base case is not reached, then the function calculates the middle index, mid, of the array from the indexes low and high. Create a new tree node with the value at mid as its data. This node becomes the root of the tree for this call of the function.
3. Make the following recursive call to add the elements from low to mid-1 for the left subtree of the root.

root.left = sorted_array_to_bst_helper(nums, low, mid - 1)

4. Make the following recursive call to add the elements from mid+1 to high for the right subtree of the root.

root.right = sorted_array_to_bst_helper(nums, mid + 1, high)

The following illustration depicts the steps above: