Question4_3.java

/**
 * Given a sorted (increasing order) array with unique integer elements,
 * write an algorithm to create a binary search tree with minimal height.
 * 
 * Time  Complexity: O(n)
 * Space Complexity: O(n)
 */

public class Question4_3 {
    public TreeNode buildBinaryTree(int[] array) {
        if (array == null || array.length == 0) {
            return null;
        }
        
        return recBuildBinaryTree(array, 0, array.length - 1);
    }
    
    private TreeNode recBuildBinaryTree(int[] array, int start, int end) {
        if (start > end) {
            return null;
        }
        
        int middle = (end - start) / 2 + start;
        TreeNode node = new TreeNode(array[middle]);
        node.left = recBuildBinaryTree(array, start, middle - 1);
        node.right = recBuildBinaryTree(array, middle + 1, end);
        
        return node;
    }
}


class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;
    
    public TreeNode() {
        this(0, null, null);
    }
    
    public TreeNode(int value) {
        this(value, null, null);
    }
    
    public TreeNode(int value, TreeNode left, TreeNode right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}