Given a sorted array, convert to BST(binary search tree_.

For example, given a sorted array [1,2,3,4,5,6,7], output should be:

     4
   /  \
  2     6
 / \   / \
1   3 5   7

The sorted array represents the inorder traversal of a tree. The middle element of an array represents to root of the tree. The elements on left of the middle element are left children of the tree and elements on the right of the middle element are right children of the tree. [1,2,3] <- 4 -> [5,6,7] Now in [1,2,3] The middle element is left child of parent node 4 and 1,3 are left and right child respectively. If we follow this pattern, then we can write a program where once the middle element is found, we recursively break the sub arrays in the nodes and attach the left child and right child respectively.

  public class ArrayToTree {
  public TreeNode sortedArrayToBST(int[] nums) {
    return sortedArrayToBST(nums, 0, nums.length);
  }
  
  public TreeNode sortedArrayToBST(int[] nums, int start, int end) {
    if (start >= end)
      return null;
    int mid = (start+end)/2;
    TreeNode root = new TreeNode(nums[mid]);
    root.left = sortedArrayToBST(nums, start, mid);
    root.right = sortedArrayToBST(nums, mid+1, end);
    return root;
  }

  class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
      val = x;
    }
  }
}