Constructing a minimum height BST with elements from a sorted array.

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

Algorithm:

1. Pass the array reference, starting index (s) and end index (e) recursively.
2. Calculate mid = (e+s)/2
3. Construct a new Node with array[mid] as the value.
4. Now node.left = (array, s, mid-1)
5. node.right = (array, mid+1, e)
6. Return this node.
7. Returning condition during recursion:
  if(s > e) we must return null (no element to be placed there)
  if(s==e) return new Node(array[s])

Source:

public class Code{
    
    public class Node{
        int value;
        Node left, right;
        Node(){}
        Node(int value){this.value = value;}
        Node(int value, Node left, Node right){
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }
    
    Node root;
    
    void construct(int[] a){
        root = build(a, 0, a.length-1);
    }
    
    Node build(int[] a, int s, int e){
        if(s>e)return null;
        else if(s==e)return new Node(a[s]);
        else{
            int mid = (e+s)/2;
            Node node = new Node(a[mid]);
            node.left = build(a, s, mid-1);
            node.right = build(a, mid+1, e);
            return node;
        }
    }
    
    void printTree(){
        inorder(root);
        System.out.println("Balanced? : "+isBalanced()+" Height = "+checkB(root));
    }
    
    void inorder(Node node){
        if(node==null)return;
        inorder(node.left);
        System.out.println(node.value);
        inorder(node.right);
    }
    
    boolean isBalanced(){
        return checkB(root)!=-1;
    }
    
    int checkB(Node node){
        if(node == null)return 0;
        int left = checkB(node.left)+1; if(left == 0)return -1;
        int right = checkB(node.right)+1; if(right == 0)return -1;
        int diff = Math.abs(left - right); if(diff > 1)return -1;
        else return Math.max(left, right);
    }
    
    int height(Node node){
        if(node == null)return 0;
        int left = checkB(node.left)+1; if(left == 0)return -1;
        int right = checkB(node.right)+1; if(right == 0)return -1; 
        return Math.max(left, right);
    }
    
    public static void main(String[] args){ 
        Code tree = new Code();
        int a[] = {3,4,2,1}; 
        tree.construct(a);
        tree.printTree();
    }
}

Output:

3
4
2
1
Balanced? : true Height = 3