Convert sorted array to Balanced BST

Problem 

Given a sorted (increasing order) array, write an algorithm to create a binary tree with minimal height.

Examples

Input: 1 2 3 4 5 6 7

Output:

    4
   / \
  3   6
 / \ / \
3  4 6  7

Solutions

 Method 1 - Take the array's middle element and insert it recursively

• Pick up the middle element of the array
• Set it as the root
• Recursively build up left and right subtrees with lower and higher halves of the array

Here is the code in java:

public static BST sortedArrayToBST(int[] arr){
    Node bst = new Node();
    bst = sortedArrayToBST(arr, 0, arr.length-1, bst);
    return bt;
}

private static Node sortedArrayToBST(int[] arr, int start, int end) {

    if( start == end){
        bst.insert(new Node(arr[start]));
        return;
    }
    else if(start > end) {
        return;
    }
    int middle = (start+end)/2;
    Node node = new Node(arr[middle]);
    //bst.insert(new Node(arr[middle]));
    node.left = sortedArrayToBST(arr, start, middle - 1);
    node.right = sortedArrayToBST(arr, middle+1, end);
    return node;
}

Time complexity - O(n)
Space Complexity - O(1) (but if you internally think of recursion, it will be kind of O(n)