Convert Sorted Array to BST
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
Example:
Given the sorted array: [-10,-3,0,5,9],
One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:
0
/ \
-3 9
/ /
-10 5
Algorithm:
1 Since the given array is sorted, we can assume it to be the result of an inorder traversal of the given tree.
2 In which case the mid value of the given sorted array would represent the root of one possible BST that can be constructed from the given array elements.
3 To be in alignment with the definition of a Binary Search Tree, the elements in the array to the left of the mid value, would contribute to the left subtree of our root while the elements in the array to the right of the mid value, would contribute to the right subtree of our root.
4 Hence we can recursively construct out binary search tree, by using binary search algorithm on the array, to construct the root, left and right subtree respectively by recursively invoking the convertToBstHelper method with appropriate boundary conditions, that of low, mid -1 for the left subtree and mid+1, high for the right subtree.
5 The base condition that would terminate the recursion would then be if low boundary index exceeds high boundary index, in which case return null.
Test:
1 Test with sanity input like null or empty values.
2 Test with negative and positive array elements.
3 Test after constructing the BST, whether the in order of the constructed tree returns back the array elements or not.
Solution:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return helper(nums, 0, nums.length - 1);
}
private TreeNode helper(int[] nums, int low, int high) {
if(low > high) {
return null;
}
int mid = low + (high - low)/2;
//center val of sorted array as the root of the bst
TreeNode head = new TreeNode(nums[mid]);
//left of the mid value should go to the left of this root node to satisfy bst
head.left = helper(nums, low, mid - 1);
//right of the mid value should go to the right of this root node to satisfy bst
head.right = helper(nums, mid + 1, high);
return head;
}
//T O(log n) S O(n) recursion stack space
}
//https://gist.github.com/harycane/d7e6505ea6cbb6e9fd6c954cbdcf2216
Complexity Analysis:
Since we perform binary search on the array elements, splitting the input size by half through each recursion, therefore the time complexity that would be incurred from the aforementioned algorithm would be same as that incurred in binary search, that of T O(log n). Space complexity due to recursion stack space would incur in the worst case of S O(n).