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 take a sorted array of three elements as an example to explain the solution. In this array, the first element will be smaller than the middle element, and the right element will be 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 right child of the root. This approach can be used to create the BST from a sorted array.

The first step of constructing the BST from the sorted array is to find the middle element of the array and create the root node from that element. Then, calculate the middle element from the left subarray, and make it the left node of the root. Recursively, do these steps on the left subarray to create the left subtree. Next, calculate the middle element from the right subarray, and make it the right node of the root. Recursively, do these steps on the right subarray to create the right subtree.

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 = SortedArrayToBstHelper(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 = SortedArrayToBstHelper(nums, mid + 1, high)

The following illustration depicts the steps above: