Convert Sorted Array to Binary Search Tree

Posted on

Given an array where elements are sorted in ascending order, convert 
it to a height balanced BST.
1 2 3 4 5 6 7 8 

         4
      2     6  
     1      3      5    7
                8

1 2 3 4 5 6 7 8 9 10 11 12 
         
         6
      3     9
    1   4      7       11
       2    5   8 10  12

*/

public class sortedArrayToBST{
   public static TreeNode sortedArrayToBST(int[] nums) {
        if (nums.length == 0) {return null;}

        int low = 0;
        int high = nums.length - 1;
       
        return helper(nums, low, high);
    }

    public static TreeNode helper(int[] nums, int l, int h) {
       if (l > h) {return null;}
       int m = (l + h) / 2;
       TreeNode root = new TreeNode (nums[m]);
    
       root.left = helper(nums, l, m - 1);
       root.right = helper(nums, m + 1, h);
       return root;
    }


   public static void main(String[] args) {
      int[] a = new int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
      TreeNode root = sortedArrayToBST(a);
   }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
 }
First, one must be clear about what is a height balanced BST.
1. BST must satisfy value of left child <= root value <= value of right child.
2. Height balance means the height difference between the left subtree and right subtree can not be more than 1.
Therefore, mid value must be root from the start. Each time within each half in the array, always the mid point is root of the subtree. For tree problems, recursion is the best solution. So the same helper method can be applied to subtrees on and on. For the left half, the high boundary changes. Calculate new middle, and apply (middle – 1) as the new high boundary. For the right half, the low boundary changes. Calculate new middle, and apply (middle + 1) as the new low boundary.
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s