CareerCup_4.1 - BalancedBinaryTree

BalanceChecker..java

//check https://gist.github.com/chrislukkk/2a1f825b8e924ea773e8 for binary tree and tree builder
package Chapter4;

public class BalanceChecker {
    public static <T extends Comparable<T>> boolean isBalanced(
	    BinaryTree<T> tree) {
	return getBalancedHeight(tree.root()) >= 0;
    }

    public static <T extends Comparable<T>> int getBalancedHeight(TreeNode<T> node) {
	if (node == null)
	    return 0;
	
	//check if left tree balanced and return height
	int leftSubTreeHeight = getBalancedHeight(node.left);
	if (leftSubTreeHeight < 0)
	    return -1;
	
	//check if right tree balanced and return height
	int rightSubTreeHeight = getBalancedHeight(node.right);
	if (rightSubTreeHeight < 0)
	    return -1;

	//return -1 if the subtree rooted by node is not balanced
	if (Math.abs(leftSubTreeHeight - rightSubTreeHeight) > 1)
	    return -1;

	return Math.max(leftSubTreeHeight, rightSubTreeHeight) + 1;
    }
    
    public static void main(String[] args) {
	/*	_______7______
	       /              \
	    __10__          ___2
	   /      \        /
	   4       3      _8
	            \    /
	             1  11 		*/
	Integer[] pre = { 7, 10, 4, 3, 1, 2, 8, 11 };
	Integer[] in = { 4, 10, 3, 1, 7, 11, 8, 2 };
	BinaryTree<Integer> unbalancedTree = BinaryTreeBuilder.buildTree(pre, in);
	System.out.println("Tree one is " + (isBalanced(unbalancedTree) ? "balanced" : "unbalanced"));
	
	/*	_______7______
	       /              \
	    __10__          ___2
	   /      \        /
	   4       3      8
	          / \       
	         5   1   		*/
	Integer[] pre2 = { 7, 10, 4, 3, 5, 1, 2, 8 };
	Integer[] in2 = { 4, 10, 5, 3, 1, 7, 8, 2 };
	BinaryTree<Integer> balancedTree = BinaryTreeBuilder.buildTree(pre2, in2);
	System.out.println("Tree one is " + (isBalanced(balancedTree) ? "balanced" : "unbalanced"));
    }
}