Balanced Binary Tree: Solution Explained

The Balanced Binary Tree problem evaluates whether you understand tree traversal patterns and the efficiency considerations behind recursive algorithms. Although the definition of a “balanced” tree is simple, a naive approach can lead to excessive repeated work. Interviewers often use this problem to see if you can optimize recursive tree checks through bottom-up computation.

This problem is a great example of detecting structure violations during traversal and short-circuiting early when imbalance is found.

---

Problem

You are given the root of a binary tree. Your task is to:

• Return true if the tree is height-balanced
• Return false otherwise

A binary tree is considered height-balanced if, for every node:

• The height difference between its left and right subtrees is no more than one, and
• Both subtrees are themselves balanced

Height is defined as the number of edges on the longest path down to a leaf.

---

Example 1

Input:

3
/
9 20
/
15 7

Output:

true

Explanation:

This tree’s left and right subtrees differ in height by at most one at every node.

---

Example 2

Input:

1
/ \
2 2
/
3 3
/
4 4

Output:

false

Explanation:

The left subtree is significantly deeper than the right subtree, breaking the balance condition.

---

Solution

A naive solution computes the height of each subtree separately and checks balance at every node. However, this leads to repeated height calculations and results in an O(n²) worst-case time complexity.

Instead, we use a bottom-up approach that computes height while simultaneously checking balance. This allows us to detect imbalance early and avoid unnecessary work.

---

Key Idea

Create a recursive helper that returns:

• The height of the subtree if it is balanced
• -1 if the subtree is not balanced

This way:

• As soon as -1 is encountered, failure is propagated upward
• No repeated height computation is needed
• The problem is reduced to a clean O(n) traversal

---

Why This Works

The height of a subtree only matters if the subtree is balanced. The moment we detect an imbalance, the exact height no longer matters—we immediately return -1 and stop further computation.

This enables:

• A single DFS traversal
• O(n) time complexity
• Constant extra space beyond the recursion stack

This is the standard optimized solution expected in interviews.

---

Algorithm Outline

Define a recursive helper check(node):

1. If node is None, return height 0
2. Recursively compute the height of the left subtree
   • If it returns -1, propagate upward
3. Recursively compute the height of the right subtree
   • If it returns -1, propagate upward
4. If the height difference is greater than 1, return -1
5. Otherwise, return 1 + max(left_height, right_height)

In the main function, return:

check(root) != -1

---

Sample Implementation (Python)

def isBalanced(root):
    def check(node):
        if not node:
            return 0

        left = check(node.left)
        if left == -1:
            return -1

        right = check(node.right)
        if right == -1:
            return -1

        if abs(left - right) > 1:
            return -1

        return 1 + max(left, right)

    return check(root) != -1

---

Complexity Analysis

• Time Complexity: O(n) — each node is visited once
• Space Complexity: O(h) for the recursion stack
  • O(log n) for balanced trees
  • O(n) for skewed trees

---

Alternative Solution: Top-Down (Less Efficient)

A top-down approach computes height at each node and checks balance separately. While simpler to write, it suffers from:

• Repeated height computations
• Worst-case time complexity: O(n²)

Interviewers generally expect the bottom-up approach.

---

Interview Insight

This problem tests your ability to:

• Recognize overlapping subproblems in tree recursion
• Avoid recomputation by combining checks and height calculations
• Build efficient bottom-up recursive solutions
• Short-circuit execution when an invalid structure is detected

This technique—returning a special flag (-1) to signal invalidity—appears frequently in tree problems such as:

• Validating Binary Search Trees
• Computing tree diameters
• Verifying subtree structure