cc150_4_1.java

package cc150_4_1;

public class BalanceTree<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 BalanceTree(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 (checkheight(root) == -1) return false;
		else
			return true;
	}
	
	private int checkheight(Node root) {
		if (root == null)
			return 0;
		
		// Check if left is balanced
		int leftheight = checkheight(root.left);
		if(leftheight == -1){
			return -1;
			}
		//Check if right is balanced
		int rightheight = checkheight(root.right);
		if(rightheight == -1) return -1;
		
		// Check current
		int heightDiff = leftheight -rightheight;
		if(Math.abs(heightDiff) > 1){
			return -1;
		}
		else{
			return Math.max(leftheight,rightheight) +1;
		}
		
	}
	
	
	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,15};
		/*						7
		 *                     / \
		 *                    /   \ 
		 *		     
		 *                  4       9
		 *                 / \     / \
		 *                2   5   8   10
		 *               / \   \       \
		 *              1   3   6       11
		 *             /
		 *            0
		 */                  
		BalanceTree<Integer> test = new BalanceTree<Integer>(data);
		if (test.isBalanced())
			System.out.println("Balanced");
		else System.out.println("Not Balanced");
 
	}
}