[CC150][4.1/4th e.d] Implement a function to check if a tree is balanced For the purposes of this question, a balanced tree is defined to be a tree such that no two leaf nodes differ in distance from the root by more than one.

BST.java

public class BST<Key extends Comparable<Key>> {
	private Node root;
	
	private class Node {
		private Key key;
		private Node left, right;
		
		public Node(Key key) 
		{ this.key = key; }
	}
	
	public BST(Key[] keys) {
		for (Key key : keys)
			put(key);
	}
	
	public void put(Key key) {
		root = put(root, key);
	}
	
	private Node put(Node x, Key key) {
		if (x == null) return new Node(key);
		int cmp = key.compareTo(x.key);
		if (cmp < 0) x.left = put(x.left, key);
		else if (cmp > 0) x.right = put(x.right, key);
		return x;
	}
	
	public boolean isBalanced() {
		if (root == null) return true;
		int[] lv = countLv(root);
		System.out.println(lv[0]+" "+lv[1]);
		if ((lv[0] - lv[1]) >= 2) return false;
		return true;
	}
	
	private int[] countLv(Node x) {
		int[] result = {0,0};
		if (x == null)
			return result;
		int[] countNextLeft = countLv(x.left);
		int[] countNextRight = countLv(x.right);
		result[0] = Math.max(countNextLeft[0], countNextRight[0]) + 1;
		result[1] = Math.min(countNextLeft[1], countNextRight[1]) + 1;
		
		return result;
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Integer data[] = {7,4,9,2,5,8,10,1,3,6,11,0};
		/*			7
		 *                     / \
		 *                    /   \ 
		 *		     /	   \
		 *                  4       9
		 *                 / \     / \
		 *                2   5   8   10
		 *               / \   \       \
		 *              1   3   6       11
		 *             /
		 *            0
		 */                  
		BST<Integer> test = new BST<Integer>(data);
		if (test.isBalanced())
			System.out.println("Balanced");
		else System.out.println("Not Balanced");

	}

}