CC_4_1

BalancedBinaryTree.java

// Cracking the Coding Interview
// 4.1 Implement a function to check if a binary tree is balanced. 
// For the purposes of this question, a balanced tree is defined to be a tree such that 
// the heights of the two subtrees of any node never differ by more than one.
class Node {
	public Node left;
	public Node right;
	public int val;
	Node(int v) {
		val = v;
		left = null;
		right = null;
	}
}
class BalancedBinaryTree {
	public static boolean isBalanced(Node root) {
		return isBalancedHandler(root) != -1;
	}

	private static int isBalancedHandler(Node root) {
		if (root == null) {
			return 0;
		}
		int left = isBalancedHandler(root.left);
		if (left == -1) {
			return -1;
		}
		int right = isBalancedHandler(root.right);
		if (right == -1) {
			return -1;
		}

		if (Math.abs(left-right) > 1) {
			return -1;
		} else {
			return Math.max(left, right)+1;
		}
	}

	public static void main(String[] args) {
		Node test = new Node(0);
		assert isBalanced(test);
		test.left = new Node(1);
		assert isBalanced(test);
		test.left.left = new Node(2);
		assert !isBalanced(test);
		test.right = new Node(3);
		assert isBalanced(test);
		test.left.left.left = new Node(4);
		assert !isBalanced(test);
		test.right.right = new Node(5);
		test.left.right = new Node(6);
		assert isBalanced(test);

		System.out.println("Tests Passed");
	}
}