#CC150 #CC150-chap4 #tree 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.

BalancedBinaryTree

package chap4;

//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.
public class BalancedBinaryTree {

	/**
	 * Do it according to the definition, recurse through the tree, for each
	 * node, calculate the depth of each of its subtree
	 * 
	 * Time: O(n^2) because getHeight is called repeatedly on the same nodes
	 * Space: O(n)?
	 * 
	 * @param root
	 * @return
	 */
	public boolean isBalancedSlow(TreeNode root) {
		// Base Case
		if (root == null) {
			return true;
		}
		//
		if (Math.abs(getHeight(root.left) - getHeight(root.right)) > 1) {
			return false;
		} else {
			// Recursive Case
			return (isBalancedSlow(root.left) && isBalancedSlow(root.right));
		}
	}

	private int getHeight(TreeNode n) {
		// Base Case
		if (n == null) {
			return 0;
		} else {
			return Math.max(getHeight(n.left), getHeight(n.right)) + 1;
		}

	}

	/**
	 * Get and check height at the same time O(N) time, O(lgN) space, lgN is the
	 * max Depth
	 * 
	 * @param root
	 * @return
	 */
	public boolean isBalancedFast(TreeNode root) {
		if (checkHeight(root) == -1) {
			return false;
		}
		return true;
	}

	// Check if the treenode is balanced
	private int checkHeight(TreeNode n) {
		// Base case
		if (n == null) {
			return 0;// set the height as 0
		}
		// Check if left is balanced
		int leftHeight = checkHeight(n.left);
		if (leftHeight == -1) {// not balanced
			return -1;
		}
		// Check if right is balanced
		int rightHeight = checkHeight(n.right);
		if (rightHeight == -1) {
			return -1;
		}
		// Check current
		if (Math.abs(leftHeight - rightHeight) > 1) {
			return -1;
		} else {
			// return the true height
			return Math.max(leftHeight, rightHeight) + 1;
		}
	}
	
	// Testing
	public static void main(String[] args) {
		BalancedBinaryTree tester = new BalancedBinaryTree();
		// root1: 1,2,#,3,#
		TreeNode root1 = new TreeNode(1);
		root1.left = new TreeNode(2);
		root1.left.left = new TreeNode(3);
		System.out.println(tester.isBalancedFast(root1));
		// root2: 1,2,2,3,#
		TreeNode root2 = new TreeNode(1);
		root2.left = new TreeNode(2);
		root2.right = new TreeNode(2);
		root2.left.left = new TreeNode(3);
		System.out.println(tester.isBalancedFast(root2));
	}

}