ArrayToBST.java

//http://coolcodebro.blogspot.com/2012/12/sorted-array-to-binary-search-tree.html

public class ArrayToBST {
  public static void main(String[] args) {
		new ArrayToBST().run();
	}
	
	void run() {
		int[] arr = {0, 4, 5, 6, 7, 9, 10, 15, 20};		
		TreeNode root = buildBst(arr, 0, arr.length-1);
		printInOrder(root);
	}
	
	//Returns the root tree node
	TreeNode buildBst(int[] arr, int low, int high) {
		if(high < low)
			return null;

		TreeNode node = new TreeNode();
		int mid = (high + low) / 2;
		
		node.value = arr[mid];
		node.left = buildBst(arr, low, mid-1);
		node.right = buildBst(arr, mid+1, high);
		
		return node;
	}
	
	//For testing purposes: if prints in ascending order - means correct BST
	void printInOrder(TreeNode root) {
		if(root == null)
			return;
		
		printInOrder(root.left);
		System.out.print(root.value + " ");
		printInOrder(root.right);
	}
}

class TreeNode {
	int value;
	TreeNode left;
	TreeNode right;
}