[CC150][4.3] Given a sorted (increasing order) array, write an algorithm to create a binary tree with minimal height.

BST.java

import java.util.LinkedList;

public class BST<Key extends Comparable<Key>> {
	private Node root;
	
	private class Node {
		Key key;
		Node left, right;
		
		public Node(Key key) {
			this.key = key;
		}
	}
	
	public BST(Key[] keys) {
		root = put(root, 0, keys.length - 1, keys);
	}
	
	/* always put median of [low,...,high] in current node */
	private Node put(Node x, int low, int high, Key[] keys) {
		if (low > high) return null;
		int mid = (high - low) / 2 + low;
		if (x == null) {
			x = new Node(keys[mid]);
			x.left = put(x.left, low, mid - 1, keys);
			x.right = put(x.right, mid + 1, high, keys);
		}
		return x;
	}
	
	public Iterable<Key> traverseInOrder() {
		LinkedList<Key> list = new LinkedList<Key>();
		inOrder(root, list);
		return list;
	}
	
	private void inOrder(Node x, LinkedList<Key> list) {
		if(x == null) return;
		inOrder(x.left, list);
		list.add(x.key);
		inOrder(x.right, list);
	}
	
	public int calcHeight() {
		return calcHeight(root);
	}
	
	private int calcHeight(Node x) {
		if (x == null) return 0;
		return Math.max(calcHeight(x.left), calcHeight(x.right)) + 1;
	}
	
	public static void main(String[] args) {
		Integer[] data = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
		BST<Integer> test = new BST<Integer>(data);
		for (Integer key : test.traverseInOrder())
			System.out.print(key + " ");
		System.out.print("\n");
		System.out.println(test.calcHeight());
	}
}