Create a binary search tree from a sorted array (increasing order)

Question

Description:

Since the input array is sorted, we can take the middle element of the array to be parent and recursively do the same on the left and right halves to create left and right sub trees of the parent.

class Node{
        int data;
        Node left;
        Node right;
        Node(int x)
        {
            data = x;
        }
    }
    public class createBSTFromSortedArray {

        public static Node getBST(int[] sortedArray, int start, int end)
        {
            if(start <= end)
            {
            int mid = (start+end)/2;
            Node root = new Node(sortedArray[mid]);
            root.left = getBST(sortedArray,start,mid-1);
            root.right = getBST(sortedArray, mid+1,end);
            return root;
            }
            return null;
        }

        public static void printTree(Node root)
        {
            if(root == null)
            {
                return ;
            }

            printTree(root.left);
            System.out.println(root.data);
            printTree(root.right);
        }
        public static void main(String[] args) {
            int[] input = {};
            Node root = getBST(input, 0 , input.length - 1);
            printTree(root);
            }
    }

Answer 1

Space and indentation

Your indentation and use of spaces is terrible. This document may help you improve your Java coding style.

Possible overflow

You solution may cause overflow and unexpected results for big enough inputs in this line:

int mid = (start + end) / 2;

changing it to this will solve the problem:

int mid = start + (end - start) / 2;

---

Also returning null early looks cleaner IMO

public static Node getBST(int[] sortedArray, int start, int end) {
    if(start > end) { 
        return null;
    }
    int mid = start + (end - start) / 2;
    Node root = new Node(sortedArray[mid]);
    root.left = getBST(sortedArray, start, mid - 1);
    root.right = getBST(sortedArray, mid + 1, end);
    return root;    
}