Solution: Convert Sorted Array to Binary Search Tree
Let's solve the Convert Sorted Array to Binary Search Tree problem using the Tree Depth-First Search pattern.
We'll cover the following
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:
-
nums.length
-
nums[i]
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:
- The base case is
low > high
, meaning no more elements remain to add to the tree. Therefore, returnNULL
. - If the base case is not reached, then the function calculates the middle index,
mid
, of the array from the indexeslow
andhigh
. Create a new tree node with the value atmid
as its data. This node becomes the root of the tree for this call of the function. - Make the following recursive call to add the elements from
low
tomid-1
for the left subtree of the root.
root.left = SortedArrayToBstHelper(nums, low, mid - 1)
- Make the following recursive call to add the elements from
mid+1
tohigh
for the right subtree of the root.
root.right = SortedArrayToBstHelper(nums, mid + 1, high)
The following illustration depicts the steps above:
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.