package tree;

/**
 * Created by gouthamvidyapradhan on 09/03/2017. Given an array where elements are sorted in
 * ascending order, convert it to a height balanced BST.
 */
public class ConvertSortedArrayToBST {
  public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

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

  public TreeNode sortedArrayToBST(int[] nums) {
    if (nums.length == 0) return null;
    return build(0, nums.length - 1, nums);
  }

  private TreeNode build(int s, int e, int[] nums) {
    if (s > e) return null;

    int m = (e - s) / 2;
    int node = nums[s + m];
    TreeNode root = new TreeNode(node);
    if (s == e) return root;

    root.left = build(s, s + m - 1, nums);
    root.right = build(s + m + 1, e, nums);

    return root;
  }
}