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 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:
- 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.