up vote 0 down vote favorite

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);
            }
    }
share|improve this question
    
Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. – Simon Forsberg♦ Apr 24 '16 at 14:55
up vote 1 down vote accepted

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;    
}
share|improve this answer
    
Thanks for the suggestions. I will try to incorporate these into my code. – saneGuy Apr 9 '16 at 18:59
    
@saneGuy you know you can upvote too ;-) – janos♦ Dec 4 '16 at 18:10

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.