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

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);
}
}

• 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. Apr 24, 2016 at 14:55

Space and indentation

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;
}

• Thanks for the suggestions. I will try to incorporate these into my code. Apr 9, 2016 at 18:59