148. Balanced Binary Tree

🔗 LeetCode Problem: 110. Balanced Binary Tree
📊 Difficulty: Easy
🏷️ Topics: Binary Trees, DFS, Height Calculation, Recursion

Problem Statement

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

A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: true

Example 2:

Input: root = [1,2,2,3,3,null,null,4,4]
Output: false

Example 3:

Input: root = []
Output: true

Constraints: - The number of nodes in the tree is in the range [0, 5000] - -10^4 <= Node.val <= 10^4

🌳 Visual Understanding - What is "Balanced"?

Definition:

Height-balanced means:
  For EVERY node in tree:
    |height(left) - height(right)| <= 1

Must check ALL nodes, not just root!

Example 1 - Balanced Tree:

Tree:
         3
        / \
       9   20
          /  \
         15   7

Check each node:

Node 9:
  left: null (height 0)
  right: null (height 0)
  |0 - 0| = 0 <= 1 ✓

Node 15:
  left: null (height 0)
  right: null (height 0)
  |0 - 0| = 0 <= 1 ✓

Node 7:
  left: null (height 0)
  right: null (height 0)
  |0 - 0| = 0 <= 1 ✓

Node 20:
  left: 15 (height 1)
  right: 7 (height 1)
  |1 - 1| = 0 <= 1 ✓

Node 3 (root):
  left: 9 (height 1)
  right: 20 (height 2)
  |1 - 2| = 1 <= 1 ✓

ALL nodes balanced → Tree is balanced! ✓

Example 2 - Unbalanced Tree:

Tree:
         1
        /
       2
      /
     3

Check each node:

Node 3:
  left: null (height 0)
  right: null (height 0)
  |0 - 0| = 0 <= 1 ✓

Node 2:
  left: 3 (height 1)
  right: null (height 0)
  |1 - 0| = 1 <= 1 ✓

Node 1 (root):
  left: 2 (height 2)
  right: null (height 0)
  |2 - 0| = 2 > 1 ✗ UNBALANCED!

One node unbalanced → Tree is unbalanced! ✗

Visual with Heights:

BALANCED:
       3 (h=3)
      / \
(h=1)9   20(h=2)
        /  \
  (h=1)15  7(h=1)

At each node: |left_h - right_h| <= 1 ✓

UNBALANCED:
       1 (h=3)
      /
     2 (h=2)
    /
   3 (h=1)

At root: |2 - 0| = 2 > 1 ✗

Key Insight:

To check if tree balanced:
  1. Calculate height of left subtree
  2. Calculate height of right subtree
  3. Check if |left_h - right_h| <= 1
  4. Recursively check left and right subtrees

Height calculation is KEY! 📏

🧠 The AHA Moment - Two Approaches

Approach 1: Naive (Inefficient but Clear)

For each node:
  1. Calculate left height (traverse left subtree)
  2. Calculate right height (traverse right subtree)
  3. Check balance at current node
  4. Recursively check left and right

Problem: Recalculates heights multiple times!
Time: O(n²) ✗

Approach 2: Optimized (Efficient!)

Return TWO pieces of info from each node:
  1. Is this subtree balanced?
  2. What is the height?

Combine calculation and check in ONE traversal!
Time: O(n) ✓

Similar to Problem 147 (Max Path Sum):
  - Return different info than what we check
  - Bottom-up approach
  - Post-order traversal

🧠 Recursive Thinking - Building Solutions

Base Case:

What's the simplest case?
  → null node

Is null balanced?
  → YES! (vacuously true)

What's its height?
  → 0 (no nodes)

if (node == null) return 0 (or true, or special value)

Recursive Case - Naive Approach:

For any node:

STEP 1: Check if node itself is balanced
  leftHeight = height(node.left)
  rightHeight = height(node.right)

  if (|leftHeight - rightHeight| > 1):
    return false

STEP 2: Check if children are balanced
  if (!isBalanced(node.left)):
    return false
  if (!isBalanced(node.right)):
    return false

STEP 3: All checks pass
  return true

Recursive Case - Optimized Approach:

For any node:

STEP 1: Get info from children
  leftInfo = checkHeight(node.left)
  rightInfo = checkHeight(node.right)

STEP 2: Check if children unbalanced
  if (leftInfo == -1 or rightInfo == -1):
    return -1  // Propagate unbalanced

STEP 3: Check current node balance
  if (|leftInfo - rightInfo| > 1):
    return -1  // Current unbalanced

STEP 4: Return height for parent
  return 1 + max(leftInfo, rightInfo)

🎯 Solution 1: Naive Approach (O(n²))

Implementation:

class Solution {
    public boolean isBalanced(TreeNode root) {
        // Base case: null tree is balanced
        if (root == null) {
            return true;
        }

        // STEP 1: Check if current node is balanced
        // Calculate heights of left and right subtrees
        int leftHeight = height(root.left);
        int rightHeight = height(root.right);

        // Check balance condition at current node
        if (Math.abs(leftHeight - rightHeight) > 1) {
            return false;  // Current node unbalanced!
        }

        // STEP 2: Recursively check if children are balanced
        // Both subtrees must be balanced
        return isBalanced(root.left) && isBalanced(root.right);
    }

    // Helper: Calculate height of tree
    private int height(TreeNode node) {
        // Base case: null has height 0
        if (node == null) {
            return 0;
        }

        // Height = 1 + max of children heights
        int leftHeight = height(node.left);
        int rightHeight = height(node.right);

        return 1 + Math.max(leftHeight, rightHeight);
    }
}

Why O(n²)?

For each node (n nodes total):
  - Call height() which visits all descendants
  - In worst case: O(n) work per node

Total: O(n) × O(n) = O(n²)

Example - Skewed tree:
       1
      /
     2
    /
   3
  /
 4

At node 1: height() visits 4 nodes
At node 2: height() visits 3 nodes
At node 3: height() visits 2 nodes
At node 4: height() visits 1 node

Total: 4 + 3 + 2 + 1 = 10 operations for 4 nodes
Pattern: O(n²)

🎯 Solution 2: Optimized Approach (O(n))

The Key Insight:

Instead of:
  1. Calculate height
  2. Check balance separately

Combine them:
  Calculate height AND check balance together!

Return value indicates:
  - If >= 0: Height of balanced subtree
  - If -1: Subtree is unbalanced

Use -1 as sentinel value! 🎯

Implementation:

class Solution {
    public boolean isBalanced(TreeNode root) {
        // If checkHeight returns -1, tree is unbalanced
        // Otherwise, tree is balanced
        return checkHeight(root) != -1;
    }

    private int checkHeight(TreeNode node) {
        // Base case: null node has height 0
        // AND is balanced (vacuously true)
        if (node == null) {
            return 0;
        }

        // STEP 1: Check left subtree
        // Get height AND check if balanced
        int leftHeight = checkHeight(node.left);

        // If left subtree unbalanced, propagate upward
        // WHY? No need to check further, already unbalanced
        if (leftHeight == -1) {
            return -1;
        }

        // STEP 2: Check right subtree
        // Get height AND check if balanced
        int rightHeight = checkHeight(node.right);

        // If right subtree unbalanced, propagate upward
        if (rightHeight == -1) {
            return -1;
        }

        // STEP 3: Check if current node is balanced
        // Both children balanced, check current node
        if (Math.abs(leftHeight - rightHeight) > 1) {
            return -1;  // Current node unbalanced!
        }

        // STEP 4: Current node balanced, return height
        // Height = 1 (current) + max of children
        return 1 + Math.max(leftHeight, rightHeight);
    }
}

Why O(n)?

Visit each node exactly ONCE!

At each node: O(1) operations
  - Compare heights
  - Return value

Total: n × O(1) = O(n)

Much better! ✓

🔍 Detailed Dry Run - Optimized Approach

Complete Recursion Flow:

═══════════════════════════════════════════════════
CALL STACK VISUALIZATION
═══════════════════════════════════════════════════

Level 0: checkHeight(3)
│
├─ LEFT: checkHeight(9) ───────────────────────────┐
│                                                   │
│  Level 1: checkHeight(9)                         │
│  │                                                │
│  ├─ node = 9                                     │
│  │                                                │
│  ├─ LEFT: checkHeight(null) → return 0          │
│  ├─ leftHeight = 0                               │
│  │                                                │
│  ├─ RIGHT: checkHeight(null) → return 0         │
│  ├─ rightHeight = 0                              │
│  │                                                │
│  ├─ Check balance: |0 - 0| = 0 <= 1 ✓           │
│  │                                                │
│  └─ return 1 + max(0, 0) = 1                    │
│                                                   │
├─ RIGHT: checkHeight(20) ─────────────────────────┐
│                                                   │
│  Level 1: checkHeight(20)                        │
│  │                                                │
│  ├─ node = 20                                    │
│  │                                                │
│  ├─ LEFT: checkHeight(15) ────────────────┐     │
│  │                                         │     │
│  │  Level 2: checkHeight(15)              │     │
│  │  │                                      │     │
│  │  ├─ node = 15                          │     │
│  │  ├─ LEFT: checkHeight(null) → 0        │     │
│  │  ├─ RIGHT: checkHeight(null) → 0       │     │
│  │  ├─ Check: |0 - 0| = 0 <= 1 ✓          │     │
│  │  └─ return 1 + max(0, 0) = 1           │     │
│  │                                         │     │
│  ├─ leftHeight = 1                         │     │
│  │                                                │
│  ├─ RIGHT: checkHeight(7) ─────────────────┐    │
│  │                                          │    │
│  │  Level 2: checkHeight(7)                │    │
│  │  │                                       │    │
│  │  ├─ node = 7                            │    │
│  │  ├─ LEFT: checkHeight(null) → 0         │    │
│  │  ├─ RIGHT: checkHeight(null) → 0        │    │
│  │  ├─ Check: |0 - 0| = 0 <= 1 ✓           │    │
│  │  └─ return 1 + max(0, 0) = 1            │    │
│  │                                          │    │
│  ├─ rightHeight = 1                         │    │
│  │                                                │
│  ├─ Check balance: |1 - 1| = 0 <= 1 ✓           │
│  │                                                │
│  └─ return 1 + max(1, 1) = 2                    │
│                                                   │
├─ Back at node 3:                                 │
├─ leftHeight = 1                                  │
├─ rightHeight = 2                                 │
│                                                   │
├─ Check balance: |1 - 2| = 1 <= 1 ✓               │
│                                                   │
└─ return 1 + max(1, 2) = 3                       │

═══════════════════════════════════════════════════
FINAL: checkHeight(3) = 3 (not -1)
ANSWER: true (balanced!) ✓
═══════════════════════════════════════════════════

Return Values at Each Node:

Node 9:  returns 1 (height, balanced)
Node 15: returns 1 (height, balanced)
Node 7:  returns 1 (height, balanced)
Node 20: returns 2 (height, balanced)
Node 3:  returns 3 (height, balanced)

All returns >= 0 → Balanced! ✓

🔍 Unbalanced Example Dry Run

Complete Recursion Flow:

Level 0: checkHeight(1)
│
├─ LEFT: checkHeight(2) ───────────────────────────┐
│                                                   │
│  Level 1: checkHeight(2)                         │
│  │                                                │
│  ├─ LEFT: checkHeight(3) ─────────────────┐     │
│  │                                         │     │
│  │  Level 2: checkHeight(3)               │     │
│  │  │                                      │     │
│  │  ├─ LEFT: checkHeight(null) → 0        │     │
│  │  ├─ RIGHT: checkHeight(null) → 0       │     │
│  │  ├─ Check: |0 - 0| = 0 <= 1 ✓          │     │
│  │  └─ return 1                            │     │
│  │                                         │     │
│  ├─ leftHeight = 1                         │     │
│  ├─ RIGHT: checkHeight(null) → 0          │     │
│  ├─ rightHeight = 0                        │     │
│  │                                                │
│  ├─ Check: |1 - 0| = 1 <= 1 ✓                   │
│  └─ return 1 + max(1, 0) = 2                    │
│                                                   │
├─ leftHeight = 2                                  │
├─ RIGHT: checkHeight(null) → 0                    │
├─ rightHeight = 0                                 │
│                                                   │
├─ Check balance: |2 - 0| = 2 > 1 ✗ UNBALANCED!   │
│                                                   │
└─ return -1  ← Sentinel value!                    │

═══════════════════════════════════════════════════
FINAL: checkHeight(1) = -1
ANSWER: false (unbalanced!) ✗
═══════════════════════════════════════════════════

Early Exit Benefit:

In this case, we found unbalanced at root
No need to check anything else!

If left subtree returned -1:
  We'd propagate immediately
  Don't even check right subtree!

This is the POWER of -1 sentinel! 🎯

📊 Complexity Analysis

Naive Approach:

Time Complexity: O(n²)

For each node: O(n) for height calculation
n nodes total
Total: O(n²)

Recalculates heights multiple times!

Space Complexity: O(h)

Recursion call stack
Best: O(log n)
Worst: O(n)

Optimized Approach:

Time Complexity: O(n)

Visit each node exactly once
O(1) work per node
Total: O(n)

Each node visited ONCE! ✓

Space Complexity: O(h)

Recursion call stack
Best: O(log n)
Worst: O(n)

Same as naive, but much faster!

⚠️ Common Mistakes

Mistake 1: Only Checking Root

// ❌ WRONG - Only checks root balance
public boolean isBalanced(TreeNode root) {
    if (root == null) return true;

    int leftH = height(root.left);
    int rightH = height(root.right);

    return Math.abs(leftH - rightH) <= 1;  // Only root!
}

// Problem: Doesn't check ALL nodes!
// Tree:     1
//          /
//         2
//        / \
//       3   4
//      /
//     5
// Root balanced (|2-0| = 2... wait, that's wrong)
// But node 2 unbalanced! ✗

// ✓ CORRECT - Check all nodes recursively
return Math.abs(leftH - rightH) <= 1 
    && isBalanced(root.left)   // Check left!
    && isBalanced(root.right); // Check right!

Mistake 2: Wrong Sentinel Value

// ❌ WRONG - Using 0 as sentinel
private int checkHeight(TreeNode node) {
    if (node == null) return 0;

    int leftH = checkHeight(node.left);
    if (leftH == 0) return 0;  // WRONG! 0 is valid height!

    // ...
}

// Problem: Can't distinguish between:
//   - Unbalanced (want to signal)
//   - Null node (height 0)

// ✓ CORRECT - Use -1 (impossible height)
if (leftH == -1) return -1;  ✓

Mistake 3: Not Propagating Unbalanced

// ❌ WRONG - Continues checking after finding unbalanced
private int checkHeight(TreeNode node) {
    if (node == null) return 0;

    int leftH = checkHeight(node.left);
    int rightH = checkHeight(node.right);

    // BUG: Doesn't check if children unbalanced!
    if (Math.abs(leftH - rightH) > 1) {
        return -1;
    }

    return 1 + Math.max(leftH, rightH);
}

// Problem: If leftH = -1, still calculates with it!
// 1 + max(-1, rightH) = wrong value!

// ✓ CORRECT - Check and propagate
if (leftH == -1) return -1;  // Check left!
if (rightH == -1) return -1; // Check right!

Mistake 4: Wrong Height Calculation

// ❌ WRONG - Forgets the +1
private int height(TreeNode node) {
    if (node == null) return 0;

    int leftH = height(node.left);
    int rightH = height(node.right);

    return Math.max(leftH, rightH);  // Missing +1!
}

// Problem: Doesn't count current node!
// Tree: [1, 2, 3]
//        1
//       / \
//      2   3
// Would calculate: max(0, 0) = 0 (WRONG!)
// Should be: 1 + max(0, 0) = 1 ✓

// ✓ CORRECT - Add 1 for current node
return 1 + Math.max(leftH, rightH);  ✓

🎯 Pattern Recognition - Height-Based Problems

Core Pattern: Post-order Height Calculation

Template for height-based problems:

private int calculateProperty(TreeNode node) {
    if (node == null) return 0;

    // Post-order: children first
    int leftValue = calculateProperty(node.left);
    int rightValue = calculateProperty(node.right);

    // Check some condition
    if (condition(leftValue, rightValue)) {
        // Handle condition
    }

    // Return property for parent
    return combine(leftValue, rightValue);
}

1. Maximum Depth (Problem 133)

Calculate height = maximum depth
Same height() function!
return 1 + max(left, right)

2. Minimum Depth (Problem 134)

Similar to height
But handle leaves differently
Edge case: one child null

3. Diameter of Binary Tree

Like Problem 147 (Max Path Sum)
Track: Path through node
Return: Height for parent
Same dual-return pattern!

4. Binary Tree Maximum Path Sum (Problem 147)

Return: Height-like value
Track: Complete path globally
Very similar structure!

When to Use This Pattern:

✓ Property depends on subtree heights
✓ Need to check all nodes
✓ Bottom-up calculation
✓ Post-order traversal natural
✓ Combine child values at parent

📝 Quick Revision Notes

🎯 Core Concept

Balanced tree = for EVERY node, |left_height - right_height| <= 1. Must check ALL nodes. Naive: Calculate height at each node separately (O(n²)). Optimized: Combine height calculation with balance check (O(n)). Use -1 as sentinel for unbalanced. Return height if balanced, -1 if not. Post-order: check children, then current.

⚡ Quick Implementation

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

    public static TreeNode buildTree(Integer[] arr) {
        if (arr == null || arr.length == 0 || arr[0] == null) {
            return null;
        }

        TreeNode root = new TreeNode(arr[0]);
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        int i = 1;
        while (!queue.isEmpty() && i < arr.length) {
            TreeNode current = queue.poll();

            // Process left child
            if (i < arr.length) {
                if (arr[i] != null) {
                    current.left = new TreeNode(arr[i]);
                    queue.offer(current.left);
                }
                i++;
            }

            // Process right child
            if (i < arr.length) {
                if (arr[i] != null) {
                    current.right = new TreeNode(arr[i]);
                    queue.offer(current.right);
                }
                i++;
            }
        }

        return root;
    }

    public static void print(TreeNode root) {
        if (root == null) {
            System.out.println("[]");
            return;
        }

        List<String> result = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node != null) {
                result.add(String.valueOf(node.val));
                queue.offer(node.left);
                queue.offer(node.right);
            } else {
                result.add("null");
            }
        }

        while (!result.isEmpty() && result.get(result.size() - 1).equals("null")) {
            result.remove(result.size() - 1);
        }

        System.out.println(result);
    }    
}

class Solution {
  public boolean isBalanced(TreeNode root) {
    return isBalancedUtil(root) == -1 ? false : true;
  }

  private int isBalancedUtil(TreeNode root) {
    if(root == null) {
      return 0; // -1 for leaf node.
    }

    // checking if left sub tree is balanced.
    int leftHeight = isBalancedUtil(root.left);
    if(leftHeight == -1) {
      return -1; // ABORT
    }

    int rightHeight = isBalancedUtil(root.right);
    if(rightHeight == -1) {
      return -1; // ABORT
    }

    if(Math.abs(leftHeight - rightHeight) <= 1) {
      // if balanced at this node, return height from this node to parent
      // current height includes current node and max of left or right subtrees.
      return 1 + Math.max(leftHeight, rightHeight);
    }

    return -1;
  }

  public static void main(String[] args) {
    Solution s = new Solution();

    System.out.println(s.isBalanced(TreeNode.buildTree(new Integer[] {3,9,20,null,null,15,7}))); // true
    System.out.println(s.isBalanced(TreeNode.buildTree(new Integer[] {1,2,2,3,3,null,null,4,4}))); // false
    System.out.println(s.isBalanced(TreeNode.buildTree(new Integer[] {}))); // true
  }
}

🔑 Key Insights

Sentinel Value Magic:

Use -1 to signal "unbalanced"

Why -1?
  - Height is always >= 0
  - -1 is impossible height
  - Clear signal: something wrong!

Return value meaning:
  >= 0: Balanced with this height
  -1: Unbalanced somewhere below

Propagates up automatically! 🎯

Optimization from O(n²) to O(n):

NAIVE: Separate calculations
  isBalanced(node)  → O(n) per node
  height(node)      → O(n) per node
  Total: O(n²)

OPTIMIZED: Combined calculation
  checkHeight(node) → O(1) per node
  Does both at once!
  Total: O(n)

Key: Calculate height WHILE checking balance
Don't traverse tree multiple times! ✨

Early Exit Power:

As soon as we find -1:
  return -1 immediately
  Don't check siblings!

Example:
    Root
    /  \
  Bad  ?

If left returns -1:
  return -1 immediately
  Don't even call right!

Saves work in unbalanced trees! 🚀

Post-order Necessity:

Why post-order?

Need children's heights BEFORE:
  - Checking current node balance
  - Calculating current node height

Post-order: Children → Parent
Perfect fit! 🎯

🎪 Memory Aid

"Check ALL nodes, not just root!"
"-1 = unbalanced sentinel!"
"Combine height + check = O(n)!"
"Post-order: children first!" ✨

⚠️ Don't Forget

Check ALL nodes (not just root!)
Use -1 sentinel (invalid height!)
Propagate -1 immediately (early exit!)
Height = 1 + max(left, right) (don't forget +1!)
Post-order (children before parent!)
Optimized beats naive (O(n) vs O(n²)!)

🎉 Congratulations!

You've mastered balanced tree checking!

What You Learned:

✅ Balanced definition - All nodes checked
✅ Height calculation - Recursive pattern
✅ Naive vs optimized - O(n²) vs O(n)
✅ Sentinel value - -1 for unbalanced
✅ Combined calculation - Height + check
✅ Post-order pattern - Children first

The Optimization Journey:

Start: Naive approach
  - Understand problem clearly
  - Separate height() and isBalanced()
  - O(n²) but correct

Optimize: Combine operations
  - Notice redundant traversals
  - Calculate once, check once
  - Use sentinel for signaling
  - O(n) optimal!

This is REAL optimization thinking! 💡

Interview Mastery:

Interviewer: "Check if tree is balanced"

Your approach:
  1. "Balanced means |left_h - right_h| <= 1 at ALL nodes"
  2. "Naive: O(n²) - calculate height at each node"
  3. "Optimized: O(n) - combine height + check"
  4. "Use -1 sentinel for unbalanced"
  5. "Post-order traversal"

  Code optimized solution in 5 minutes ✓

Shows optimization thinking! 💯

You've learned a KEY optimization pattern! 🏆✨🎯

148. Balanced Binary Tree

Problem Statement

🌳 Visual Understanding - What is "Balanced"?

Definition:

Example 1 - Balanced Tree:

Example 2 - Unbalanced Tree:

Visual with Heights:

Key Insight:

🧠 The AHA Moment - Two Approaches

Approach 1: Naive (Inefficient but Clear)

Approach 2: Optimized (Efficient!)

🧠 Recursive Thinking - Building Solutions

Base Case:

Recursive Case - Naive Approach:

Recursive Case - Optimized Approach:

🎯 Solution 1: Naive Approach (O(n²))

Implementation:

Why O(n²)?

🎯 Solution 2: Optimized Approach (O(n))

The Key Insight:

Implementation:

Why O(n)?

🔍 Detailed Dry Run - Optimized Approach

Complete Recursion Flow:

Return Values at Each Node:

🔍 Unbalanced Example Dry Run

Complete Recursion Flow:

Early Exit Benefit:

📊 Complexity Analysis

Naive Approach:

Optimized Approach:

⚠️ Common Mistakes

Mistake 1: Only Checking Root

Mistake 2: Wrong Sentinel Value

Mistake 3: Not Propagating Unbalanced

Mistake 4: Wrong Height Calculation

🎯 Pattern Recognition - Height-Based Problems

Core Pattern: Post-order Height Calculation

Related Problems:

When to Use This Pattern:

📝 Quick Revision Notes

🎯 Core Concept

⚡ Quick Implementation

🔑 Key Insights

🎪 Memory Aid

⚠️ Don't Forget

🎉 Congratulations!

What You Learned:

The Optimization Journey:

Interview Mastery: