Problem Description

Given a binary tree, you need to determine whether it is height-balanced.

A height-balanced binary tree is defined as a binary tree in which the heights of the left and right subtrees of every node differ by at most 1.

In other words, for every node in the tree:

• Calculate the height of its left subtree
• Calculate the height of its right subtree
• The absolute difference between these two heights must be at most 1
• This condition must be satisfied for all nodes in the tree, not just the root

The height of a tree is the number of edges on the longest path from the root to a leaf node. An empty tree has height 0.

For example:

• A tree with nodes [3,9,20,null,null,15,7] forming a balanced structure would return true
• A tree with nodes [1,2,2,3,3,null,null,4,4] where the left subtree is much deeper than the right would return false

The solution uses a clever optimization: instead of checking balance and calculating height separately for each node, it combines both operations. The helper function returns -1 to indicate an imbalanced subtree, which allows early termination without checking all nodes unnecessarily. If any subtree is unbalanced, the entire tree is unbalanced.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: A binary tree is a special type of graph where each node has at most two children and there are no cycles.

Is it a tree?

• Yes: The problem explicitly states we're working with a binary tree structure.

DFS

• Yes: We arrive at DFS (Depth-First Search) as the recommended approach.

Conclusion: The flowchart suggests using DFS for this problem. This makes perfect sense because:

1. We need to traverse the entire tree to check if every node satisfies the balance condition
2. We need to calculate heights from the bottom up (leaves to root), which naturally fits a post-order DFS traversal
3. DFS allows us to recursively compute the height of each subtree while simultaneously checking the balance condition
4. The recursive nature of DFS matches the recursive structure of the tree itself

The solution implements DFS through the recursive height function, which:

• Traverses to the leaf nodes first (base case returns 0 for null nodes)
• Calculates heights while returning back up the tree
• Propagates the "unbalanced" signal (-1) immediately when detected, allowing early termination

This is why DFS is the optimal pattern for the Balanced Binary Tree problem - it efficiently combines height calculation with balance checking in a single traversal.

Intuition

The naive approach would be to check each node individually: for every node, calculate the height of its left and right subtrees, then verify if their difference is at most 1. However, this leads to redundant calculations since we'd repeatedly compute heights for the same subtrees.

The key insight is that while calculating the height of a tree, we're already visiting every node. So why not check the balance condition during the same traversal?

Think about how we calculate height recursively:

• The height of a null node is 0
• The height of any node is 1 + max(left_height, right_height)

During this calculation, we already have both left_height and right_height available. This is the perfect moment to check if abs(left_height - right_height) <= 1.

But here's the clever part: how do we signal that a subtree is unbalanced? We can't just return false because the function needs to return a height. The solution is to use a sentinel value -1 to indicate "this subtree is unbalanced."

This creates an elegant propagation mechanism:

• If any subtree returns -1, we immediately know it's unbalanced
• We can skip further calculations and propagate -1 upward
• This acts like an early termination signal that bubbles up to the root

So the function serves dual purposes:

1. When it returns a non-negative number, that's the actual height
2. When it returns -1, it signals the tree is unbalanced

This transforms an O(n²) naive solution (checking balance at each node separately) into an O(n) solution with a single post-order traversal.

Solution Approach

The solution implements a bottom-up recursive approach using DFS (post-order traversal). Here's how the implementation works:

We define a helper function height(root) that calculates the height of a binary tree while simultaneously checking for balance:

Base Case:

• If root is None, return 0 (an empty tree has height 0)

Recursive Case:

1. Recursively calculate the height of the left subtree: l = height(root.left)
2. Recursively calculate the height of the right subtree: r = height(root.right)

Balance Check: After getting both heights, we perform three checks:

• If l == -1: The left subtree is already unbalanced
• If r == -1: The right subtree is already unbalanced
• If abs(l - r) > 1: The current node violates the balance condition

If any of these conditions is true, we return -1 to signal that the tree is unbalanced.

Height Calculation: If all checks pass, the current subtree is balanced, so we return its height: 1 + max(l, r)

Final Result: The main function simply calls height(root) and checks if the result is non-negative:

• If height(root) >= 0: The tree is balanced, return True
• If height(root) == -1: The tree is unbalanced, return False

The algorithm visits each node exactly once, giving us O(n) time complexity, where n is the number of nodes. The space complexity is O(h) where h is the height of the tree, due to the recursive call stack.

The elegance of this solution lies in using -1 as a dual-purpose signal: it both indicates an unbalanced tree and allows early termination without needing additional boolean flags or separate functions.

Example Walkthrough

Let's walk through a small example to illustrate how the solution works.

Consider this binary tree:

       1
      / \
     2   3
    / \
   4   5
  /
 6

We'll trace through the recursive calls to see how the algorithm determines this tree is unbalanced.

Step-by-step execution:

1. Start with height(1) - we need to check node 1 (root)
   • First, calculate height(2) for the left subtree
2. At node 2:
   • Calculate height(4) for its left child
3. At node 4:
   • Calculate height(6) for its left child
4. At node 6:
   • height(None) for left child returns 0
   • height(None) for right child returns 0
   • Balance check: |0 - 0| = 0 ≤ 1 ✓
   • Return: 1 + max(0, 0) = 1
5. Back at node 4:
   • Left height (from node 6) = 1
   • height(None) for right child returns 0
   • Balance check: |1 - 0| = 1 ≤ 1 ✓
   • Return: 1 + max(1, 0) = 2
6. Back at node 2:
   • Left height (from node 4) = 2
   • Calculate height(5) for right child
7. At node 5:
   • height(None) for both children returns 0
   • Balance check: |0 - 0| = 0 ≤ 1 ✓
   • Return: 1 + max(0, 0) = 1
8. Back at node 2:
   • Left height = 2, Right height = 1
   • Balance check: |2 - 1| = 1 ≤ 1 ✓
   • Return: 1 + max(2, 1) = 3
9. Back at node 1:
   • Left height (from node 2) = 3
   • Calculate height(3) for right child
10. At node 3:
    • height(None) for both children returns 0
    • Balance check: |0 - 0| = 0 ≤ 1 ✓
    • Return: 1 + max(0, 0) = 1
11. Final check at node 1:
    • Left height = 3, Right height = 1
    • Balance check: |3 - 1| = 2 > 1 ✗
    • Return: -1 (unbalanced!)
12. Main function receives -1, so returns False

The tree is unbalanced because at the root node, the left subtree has height 3 while the right subtree has height 1, giving a difference of 2, which violates the balance condition.

Note how the algorithm efficiently combines height calculation with balance checking in a single traversal, and immediately returns -1 when it detects the imbalance at the root, without needing to check any remaining nodes.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm visits each node in the binary tree exactly once through a post-order traversal (visiting left subtree, right subtree, then the current node). At each node, it performs constant time operations: calculating the height difference and returning either -1 or 1 + max(l, r). Since we visit all n nodes once and perform O(1) work at each node, the overall time complexity is O(n).

Space Complexity: O(n)

The space complexity is determined by the recursive call stack. In the worst case, the tree could be completely unbalanced (e.g., a skewed tree where each node has only one child), resulting in a recursion depth equal to the number of nodes n. This would require O(n) space on the call stack. In the best case of a perfectly balanced tree, the recursion depth would be O(log n), but we consider the worst-case scenario for space complexity analysis, giving us O(n).

Common Pitfalls

1. Attempting Top-Down Approach with Separate Height Calculation

A common mistake is trying to solve this problem by checking balance at each node from top to bottom, calculating heights separately each time:

# Inefficient approach - DON'T DO THIS
def isBalanced(self, root):
    if not root:
        return True
  
    def getHeight(node):
        if not node:
            return 0
        return 1 + max(getHeight(node.left), getHeight(node.right))
  
    # Calculate height for each subtree separately
    left_height = getHeight(root.left)
    right_height = getHeight(root.right)
  
    # Check current node and recursively check children
    return (abs(left_height - right_height) <= 1 and 
            self.isBalanced(root.left) and 
            self.isBalanced(root.right))

Why this is problematic:

• Time complexity becomes O(n²) because we calculate heights repeatedly for the same nodes
• For each node, we traverse its entire subtree to get the height
• Lower nodes get visited multiple times unnecessarily

2. Forgetting to Check Subtree Balance Status

Another mistake is only checking the height difference without verifying if subtrees themselves are balanced:

# Incorrect - only checks current node's balance
def calculate_height(node):
    if node is None:
        return 0
  
    left_height = calculate_height(node.left)
    right_height = calculate_height(node.right)
  
    # WRONG: Only checking current node, ignoring subtree balance
    if abs(left_height - right_height) > 1:
        return -1
  
    return 1 + max(left_height, right_height)

The fix: Always check if either subtree returned -1 before checking the current node's balance:

# Correct version
if left_height == -1 or right_height == -1:
    return -1  # Propagate the unbalanced signal
if abs(left_height - right_height) > 1:
    return -1

3. Confusing Height with Depth or Number of Nodes

Some implementations mistakenly count nodes instead of edges:

# Incorrect - counting nodes instead of edges
def calculate_height(node):
    if node is None:
        return 0
    if node.left is None and node.right is None:
        return 1  # WRONG: leaf should have height 0, not 1

Remember:

• Height = number of edges on the longest path to a leaf
• A single node has height 0
• An empty tree has height -1 (though we use 0 for convenience in this problem)

4. Not Handling the -1 Signal Properly

When using -1 as an "unbalanced" indicator, ensure it's handled correctly:

# Incorrect final check
def isBalanced(self, root):
    return self.calculate_height(root) != -1  # Should be >= 0 for clarity
  
# Or worse - forgetting the special meaning of -1
def isBalanced(self, root):
    return self.calculate_height(root) > 0  # WRONG: height 0 is valid!

Best practice: Use >= 0 to make the intention clear that any non-negative height means the tree is balanced.