CC_4_3

SearchTree.java

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

class Node {
	public int val;
	public Node left;
	public Node right;
	Node(int v) {
		val = v;
		left = null;
		right = null;
	}
}

class SearchTree {
	public static Node constructBST(int[] arr) {
		int len = arr.length;
		return constructBSTHelper(arr, 0, len-1);
	}

	public static Node constructBSTHelper(int[] arr, int low, int high) {
		if (high < low) {
			return null;
		} else {
			int mid = low + (high - low)/2;
			Node root = new Node(arr[mid]);
			root.left = constructBSTHelper(arr, low, mid-1);
			root.right = constructBSTHelper(arr, mid+1, high);
			return root;
		}
	}
}

1. Good job!