108.Convert Sorted Array to balanced Binary Search Tree

108.?Convert Sorted Array to balanced Binary Search Tree

The tricky part is the base case . 
Write induction part first and then test arrays of different size,0,1,2,3 
And finalize the base case 


/**
 * 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) {
      if(nums.length == 0){
        return null;
      }
      
      TreeNode root = helper(nums,nums.length - 1); // nums.length - 1
      return root;
    }
  
    private TreeNode helper(int[] nums,int start,int end){
      // this base case,try 4 cases. When size is 0,3 
      if(start > end) return null;
      
      int mid = start + (end - start) / 2;
      TreeNode root = new TreeNode(nums[mid]);
      root.left = helper(nums,start,mid - 1);  // mid - 1
      root.right = helper(nums,mid + 1,end);  // mid + 1
      return root;
    }
}