Code link: https://leetcode.com/problems/balanced-binary-tree/

Constraint:

• The number of nodes in the tree is in the range [0, 5000]. This means we can use recursion?

Idea:

Note the definition of height and depth might be differnt from the official definition of Wikipedia. In this question, the depth is the number of nodes from root to that spesific node, but not the number of paths.

First we could get the height of a node's left and right subtree, and check if they are balanced. Then we could do this check recursively against current nodes' left and right tree. This is like a top-down way of search.

Code

1. Attempt 1

class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        
        int lh = getHeight(root.left);
        int rh = getHeight(root.right);
        if (Math.abs(lh - rh) > 1) {
            return false;
        }
        
        return isBalanced(root.left) && isBalanced(root.right);
    }
    
    private int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
    }
}

• Time: O(n^2). The time for getHeight() would be O(n) as we have to traverse all nodes in the case of a skew tree. This means for each recursion call, we spend O(n). And we have to do this for all the N nodes, resulting to O(n^2).
• Space: O(n). This would be equal to the max height of a tree.

2. Attempt 2
   A better way is to solve it in bottom-up way. When checking the height of a subtree, return something invalid when the tree is unbalanced. Normally tree height would never be negative, so we could return negative number in case the current subtree is unbalanced. And if there's any unbalanced subtree, it vialotes the definiton of being balanced. We simply need to return negative number all the way up.

class Solution {
    public boolean isBalanced(TreeNode root) {
        return getHeight(root) != -1;
    }
    
    private int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        int lh = getHeight(root.left);
        int rh = getHeight(root.right);
        if (lh == -1 || rh == -1 || Math.abs(lh - rh) > 1) {
            return -1;
        }
        
        return Math.max(lh, rh) + 1;
    }
}

• Time: O(n). The method getHeight() is O(n).

• Space: O(n).

• Similar problem:

  • https://leetcode.com/problems/maximum-depth-of-binary-tree/