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

CC150-4.3.java

import java.util.LinkedList;
import java.util.Queue;

public class Main{

	/**
	 * 4.3 Given a sorted (increasing order) array with unique integer elements,
	 * write an algorithm to create a binary search tree with minimal height.
	 * 
	 *  @Runtime & spaces
	 * 	runtime: O(n)
	 * 	space: O(n)
	 * 
	 */

//	public static void main(String[] args) throws Exception {
//		// TODO Auto-generated method stub
//		
//	}
	public TreeNode createBST(int[] data){
		if(data==null)
			return null;
		return createBST(0,data.length-1,data);
	}

	private TreeNode createBST(int start, int end, int[] data) {
		// TODO Auto-generated method stub
		if(end<start)
			return null;
		int mid=start+(end-start)/2;
		TreeNode newNode=new TreeNode(data[mid]);
		newNode.left=createBST(start, mid-1, data);
		newNode.right=createBST(mid+1, end, data);
		return newNode;
	}
}