Check if a tree is balanced or not

Problem Statement

Given a binary tree, determine if it is height-balanced. A height-balanced binary tree is a tree in which the depth of the left and right subtrees of every node never differs by more than 1.

Example:

• Input: Root of trees above
• Output: true for first tree, false for second tree

Approach 1: Brute Force (Check Height at Each Node)

Intuition

At each node, calculate the height of left and right subtrees. If the difference is more than 1, or if either subtree is unbalanced, the tree is unbalanced.

Algorithm

1. For each node, calculate height of left and right subtrees
2. Check if |leftHeight - rightHeight| <= 1
3. Recursively check if left and right subtrees are balanced
4. Return true only if all conditions are met

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public int height(TreeNode root) {
        if (root == null) return 0;
        return 1 + Math.max(height(root.left), height(root.right));
    }
    
    public boolean isBalancedBruteForce(TreeNode root) {
        if (root == null) return true;
        
        int leftHeight = height(root.left);
        int rightHeight = height(root.right);
        
        // Check current node and recursively check subtrees
        return Math.abs(leftHeight - rightHeight) <= 1 &&
               isBalancedBruteForce(root.left) &&
               isBalancedBruteForce(root.right);
    }
}

Complexity Analysis

• Time Complexity: O(n^2) - For each of n nodes, we calculate height O(n)
• Space Complexity: O(n) - Recursion stack in worst case

Approach 2: Optimal (Bottom-Up with Early Termination)

Intuition

Calculate height bottom-up and check balance simultaneously. If any subtree is unbalanced, return -1 immediately to signal failure.

Algorithm

1. Create a helper that returns height if balanced, -1 if not
2. If left or right subtree returns -1, propagate -1 (unbalanced)
3. If height difference > 1, return -1
4. Otherwise return height
5. Tree is balanced if final result is not -1

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    // Returns height if balanced, -1 if unbalanced
    private int checkHeight(TreeNode root) {
        if (root == null) return 0;
        
        int leftHeight = checkHeight(root.left);
        if (leftHeight == -1) return -1;  // Left subtree unbalanced
        
        int rightHeight = checkHeight(root.right);
        if (rightHeight == -1) return -1;  // Right subtree unbalanced
        
        // Check current node
        if (Math.abs(leftHeight - rightHeight) > 1) return -1;
        
        return 1 + Math.max(leftHeight, rightHeight);
    }
    
    public boolean isBalanced(TreeNode root) {
        return checkHeight(root) != -1;
    }
}

Complexity Analysis

• Time Complexity: O(n) - Each node visited exactly once
• Space Complexity: O(n) - Recursion stack in worst case (skewed tree)

Approach 3: Alternative (Using Pair/Tuple)

Intuition

Return both height and balanced status as a pair. This is cleaner than using -1 as a sentinel value.

Algorithm

1. Return a pair: (isBalanced, height)
2. Combine results from left and right subtrees
3. Current node is balanced if both subtrees are balanced AND height difference <= 1

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    // Returns [isBalanced (0 or 1), height]
    private int[] checkBalanced(TreeNode root) {
        if (root == null) return new int[]{1, 0};
        
        int[] left = checkBalanced(root.left);
        int[] right = checkBalanced(root.right);
        
        boolean isBalanced = (left[0] == 1) && (right[0] == 1) && 
                            Math.abs(left[1] - right[1]) <= 1;
        int height = 1 + Math.max(left[1], right[1]);
        
        return new int[]{isBalanced ? 1 : 0, height};
    }
    
    public boolean isBalancedAlt(TreeNode root) {
        return checkBalanced(root)[0] == 1;
    }
}

Complexity Analysis

• Time Complexity: O(n) - Each node visited exactly once
• Space Complexity: O(n) - Recursion stack

Key Takeaways

1. Definition: Balanced means height difference <= 1 at EVERY node
2. Brute force: O(n^2) due to repeated height calculations
3. Optimal: O(n) by combining height calculation with balance check
4. Two patterns: Use -1 sentinel, or return tuple/pair
5. Early termination (-1 approach) can be slightly faster in practice
6. This is LeetCode #110 - Balanced Binary Tree
7. Similar pattern used in diameter, path sum problems