LeetCode 110: Balanced Binary Tree Solution in Python Explained

Problem Statement

In LeetCode 110, you’re given the root of a binary tree. Your task is to return true if the tree is height-balanced—where the absolute difference in heights of left and right subtrees for every node is ≤ 1—or false if it’s not. This builds on BST construction like LeetCode 109: Convert Sorted List to Binary Search Tree, shifting focus to balance validation rather than creation.

Constraints

• Number of nodes: 0 <= n <= 10^4
• Node values: -2^31 <= Node.val <= 2^31 - 1

Example

Let’s see some cases:

Copy codeInput: root = [3,9,20,null,null,15,7]
      3
     / \
    9  20
       / \
      15  7
Output: true
Explanation: Heights: Left (1), Right (2), diff = 1 ≤ 1, balanced.

Copy codeInput: root = [1,2,2,3,3,null,null,4,4]
      1
     / \
    2   2
   / \
  3   3
 / \
4   4
Output: false
Explanation: Heights: Left (3), Right (1), diff = 2 > 1, unbalanced.

Copy codeInput: root = []
Output: true
Explanation: Empty tree is balanced.

These examples show we’re checking height balance.

Understanding the Problem

How do you solve LeetCode 110: Balanced Binary Tree in Python? Take root = [3,9,20,null,null,15,7]. We need to confirm it’s balanced—left subtree (9) height 1, right subtree (20,15,7) height 2, difference 1 ≤ 1, true. For [1,2,2,3,3,null,null,4,4], left height 3, right height 1, difference 2 > 1, false. This isn’t a level-order traversal like LeetCode 107: Binary Tree Level Order Traversal II; it’s about validating balance. We’ll use: 1. Bottom-Up DFS: O(n) time, O(h) space—our best solution. 2. Top-Down DFS: O(n log n) time, O(h) space—an alternative.

Let’s dive into the best solution.

Best Solution: Bottom-Up DFS Approach

Explanation

Bottom-Up DFS computes each subtree’s height recursively, checking balance at each node as it returns upward. If a subtree is unbalanced (height difference > 1), return a sentinel value (e.g., -1) to propagate the failure. This is the best solution due to its O(n) time complexity, visiting each node once, and efficient space usage, avoiding redundant height calculations.

For [3,9,20,null,null,15,7]:

• Leaf 9: Height 1.
• Leaf 15, 7: Height 1.
• Node 20: Heights 1, 1, diff = 0, total height 2.
• Node 3: Heights 1, 2, diff = 1, total height 3.
• Balanced, true.

Step-by-Step Example

Assume a TreeNode class: class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val; self.left = left; self.right = right.

Example 1: root = [3,9,20,null,null,15,7]

Goal: Return true.

• Start: isBalanced(3) → checkHeight(3).
• Step 1: root = 3.
• Left: checkHeight(9).
• Leaf 9, no children, return 1.
• Right: checkHeight(20).
• Left: checkHeight(15) → 1.
• Right: checkHeight(7) → 1.
• 20: Heights 1, 1, diff = 0 ≤ 1, return 2.
• 3: Heights 1, 2, diff = 1 ≤ 1, return 3.
• Finish: checkHeight(3) ≠ -1, return true.

Example 2: root = [1,2,2,3,3,null,null,4,4]

Goal: Return false.

• Start: checkHeight(1).
• Step 1: root = 1.
• Left: checkHeight(2).
• Left: checkHeight(3).
• Left: checkHeight(4) → 1.
• Right: checkHeight(4) → 1.
• 3: Heights 1, 1, diff = 0, return 2.
• Right: checkHeight(3) → 1.
• 2: Heights 2, 1, diff = 1, return 3.
• Right: checkHeight(2) → 1.
• 1: Heights 3, 1, diff = 2 > 1, return -1.
• Finish: checkHeight(1) = -1, return false.

Example 3: root = []

Goal: Return true.

• Start: checkHeight(None).
• Step 1: Null root, return 0.
• Finish: 0 ≠ -1, return true.

How the Code Works (Bottom-Up DFS) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

Copy codeclass TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def isBalanced(root: TreeNode) -> bool:
    # Line 1: Define helper function to compute height and check balance
    def checkHeight(node: TreeNode) -> int:
        # node = current node (e.g., root=3)

        # Line 2: Base case - empty node
        if not node:
            # If node is None (e.g., leaf’s child), height is 0
            return 0

        # Line 3: Compute left subtree height
        left_height = checkHeight(node.left)
        # Recursively gets left height (e.g., 9 → 1)
        # Returns -1 if unbalanced

        # Line 4: Check for left subtree imbalance
        if left_height == -1:
            # If left subtree is unbalanced (e.g., diff > 1), propagate failure
            return -1

        # Line 5: Compute right subtree height
        right_height = checkHeight(node.right)
        # Recursively gets right height (e.g., 20 → 2)
        # Returns -1 if unbalanced

        # Line 6: Check for right subtree imbalance
        if right_height == -1:
            # If right subtree is unbalanced, propagate failure
            return -1

        # Line 7: Check balance condition
        if abs(left_height - right_height) > 1:
            # If height difference > 1 (e.g., 3 vs. 1), unbalanced
            return -1

        # Line 8: Return total height of current subtree
        return 1 + max(left_height, right_height)
        # Height includes current node (e.g., 1 + max(1, 2) = 3 for root=3)

    # Line 9: Start validation and check result
    return checkHeight(root) != -1
    # Calls helper, returns true if height isn’t -1 (e.g., 3 → true)
    # -1 indicates imbalance detected

This detailed breakdown clarifies how bottom-up DFS efficiently validates tree balance.

Alternative: Top-Down DFS Approach

Explanation

Top-Down DFS recursively checks each node’s balance by computing left and right subtree heights using a separate height function, verifying the difference ≤ 1 at every step. It’s a straightforward alternative but less efficient, recomputing heights for each subtree, leading to O(n log n) time in balanced cases.

For [3,9,20,null,null,15,7]:

• Root 3: Left height 1, Right height 2, diff = 1.
• All nodes checked similarly, true.

Step-by-Step Example (Alternative)

For [1,2,2,3,3,null,null,4,4]:

• Step 1: root = 1.
• Left height = 3, Right height = 1, diff = 2 > 1, false.
• Finish: Return false.

How the Code Works (Top-Down DFS)

Copy codedef isBalancedTopDown(root: TreeNode) -> bool:
    def height(node: TreeNode) -> int:
        if not node:
            return 0
        return 1 + max(height(node.left), height(node.right))

    if not root:
        return True

    left_height = height(root.left)
    right_height = height(root.right)
    if abs(left_height - right_height) > 1:
        return False

    return isBalancedTopDown(root.left) and isBalancedTopDown(root.right)

Complexity

• Bottom-Up DFS:
• Time: O(n) – visits each node once.
• Space: O(h) – recursion stack, h = height.
• Top-Down DFS:
• Time: O(n log n) – height recomputed per node.
• Space: O(h) – recursion stack.

Efficiency Notes

Bottom-Up DFS is the best solution with O(n) time and O(h) space, efficiently checking balance in one pass—Top-Down DFS uses O(n log n) time due to repeated height calculations, making it a simpler but less efficient alternative.

Key Insights

• Balance: Subtree height diff ≤ 1.
• Bottom-Up: Single pass efficiency.
• Top-Down: Intuitive but redundant.

Additional Example

For root = [1,2,3,4,null,null,5]:

• Goal: true.
• Bottom-Up: Heights: 4 (1), 2 (2), 3 (2), 1 (3), diff ≤ 1.

Edge Cases

• Empty Tree: [] → true.
• Single Node: [1] → true.
• Skewed: [1,2,3] → false.

Both solutions handle these well.

Final Thoughts

LeetCode 110: Balanced Binary Tree in Python is a key balance validation challenge. The Bottom-Up DFS solution shines with its efficiency and elegance, while Top-Down DFS offers a more intuitive approach. Want more? Try LeetCode 104: Maximum Depth of Binary Tree for depth basics or LeetCode 108: Convert Sorted Array to Binary Search Tree for balanced BST creation. Ready to practice? Solve LeetCode 110 on LeetCode with [3,9,20,null,null,15,7], aiming for true—test your skills now!