Balanced Binary Tree | Leetcode

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

---

Solution: This is a trick question. We are not trying to find out if the tree is height-balanced or not. We are trying to see if each of the left and right sub-trees are height-balanced or not.

For example, the tree [1,2,2,3,null,null,3,4,null,null,4] is not height-balanced by the definition in this question, even though it looks height-balanced.

         1
        / \
       2   2
      /     \
     3       3
    /         \
   4           4

Therefore we just need to check height-balanced for each of the left and right children pairs.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;
        if (Math.abs(maxDepth(root.left) - maxDepth(root.right)) > 1) return false;
        return isBalanced(root.left) && isBalanced(root.right);
    }
    
    public int maxDepth(TreeNode node) {
        if (node == null) return 0;
        return 1 + Math.max(maxDepth(node.left), maxDepth(node.right));
    }
}