Cacher is the code snippet organizer for pro developers

//Normal solution: get height then compare
//Time O(n log n): every layer O(n),  log n layer.
//Space O(h)
public class Solution {
    public boolean isBalanced(TreeNode root) {
        // base case
        if (root == null) {
            return true;
        }
        // check if left and right subtree is balanced, and if the node itself is
        // balanced.
        return isBalanced(root.left) && isBalanced(root.right)
                && Math.abs(getHeight(root.left) - getHeight(root.right)) <= 1;
    }
}

// Optimal solution:
//Time O(n) : ?? //TODO
//Space O(h): ??
/* 
 * because height must >= 0; return height of the tree if it is balanced, return
 * -1 if it is unbalanced.
 */

public class Solution {
    public boolean isBalanced(TreeNode root) {
        return getHeightOrUnbalanced(root)>=0;
    }

    private int getHeightOrUnbalanced(TreeNode root) {
        // Base case: reaches leaf , so return height which is 0
        if (root == null) {
            return 0;
        }
        // subproblem
        int left = getHeightOrUnbalanced(root.left);
        int right = getHeightOrUnbalanced(root.right);
        // recursion rule
        // check if left and right subtree is balanced
        if (left == -1 || right == -1) {
            return -1;
        }
        // if left and right subtree is balanced, check if this layer is balanced.
        if (Math.abs(left - right) > 1) {
            return -1;
        }
        // if balanced, return the height.
        return Math.max(left,right)+1;

    }
}