Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
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 [1, 2, 3, 4, 5, 6]
One possible answer is:
4
/ \
2 5
/ \ \
1 3 6 Sorted Array to Balanced Binary Search Tree solution in Java
In a Binary search tree, all the values less than or equal to a node’s value go in the left subtree of the node, and all the values greater than the node’s value go in the right subtree of the node.
For the Binary Search Tree to be balanced, we need to make sure that we distribute values equally to the left and right subtrees of every node.
To do this, we choose the value in the middle of the array and make that the root node. The values before the mid value go in the left subtree and the values after the mid value go in the right subtree. We do this recursively to construct the balanced binary search tree.
Here is the complete solution:
import java.util.Arrays;
import java.util.List;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
public class SortedArrayToBalancedBST {
private static void traverseInorder(TreeNode node) {
if(node == null) {
return;
}
traverseInorder(node.left);
System.out.print(node.val + " ");
traverseInorder(node.right);
}
private static TreeNode insertBalanced(List<Integer> values, int start, int end) {
if(start > end) {
return null;
}
int mid = (start + end)/2;
TreeNode node = new TreeNode(values.get(mid));
node.left = insertBalanced(values, start, mid-1);
node.right = insertBalanced(values, mid+1, end);
return node;
}
public static TreeNode sortedArrayToBST(List<Integer> values) {
if(values.isEmpty()) {
return null;
}
return insertBalanced(values, 0, values.size()-1);
}
public static void main(String[] args) {
List<Integer> values = Arrays.asList(1, 2, 3, 4, 5, 6);
TreeNode root = sortedArrayToBST(values);
traverseInorder(root);
}
}