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.

CC150-4.1.java

package POJ;

public class Main{

	/**
	 * 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.
	 * 
	 *  @Runtime & spaces
	 * 	runtime: O(n)(n is the number of nodes)
	 * 	space: O(h) (h is the height of tree)
	 * 
	 */
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		System.out.println(isBalanced(null));
		TreeNode test = new TreeNode(0);
		System.out.println(isBalanced(test));
		test.left = new TreeNode(1);
		System.out.println(isBalanced(test));
		test.left.left = new TreeNode(2);
		System.out.println(isBalanced(test));
		test.right = new TreeNode(3);
		System.out.println(isBalanced(test));
		test.left.left.left = new TreeNode(4);
		System.out.println(isBalanced(test));
		test.right.right = new TreeNode(5);
		test.left.right = new TreeNode(6);
 
		System.out.println(isBalanced(test));
	}

	public static boolean isBalanced(TreeNode root) {
		return isBalancedTree(root) > 0;
	}

	private static int isBalancedTree(TreeNode root) {
		// TODO Auto-generated method stub
		if (root == null)
			return 0;
		int leftLen = isBalancedTree(root.left);
		if (leftLen < 0)
			return -1;
		int rightLen = isBalancedTree(root.right);
		if (rightLen < 0)
			return -1;
		// both subtrees are balanced, now we check the height difference
		int diff = Math.abs(rightLen - leftLen);
		if (diff > 1)
			return -1;
		else
			return Math.max(leftLen, rightLen) + 1;
	}
}