Balanced Binary Tree

Problem

Given the root of a binary tree, decide whether it is height-balanced: at every node, the heights of the left and right subtrees differ by at most 1. Return True if the whole tree satisfies this, False otherwise. An empty tree counts as balanced.

Note the condition must hold at every node, not just the root — a tree can look balanced from the top while hiding a lopsided subtree deeper down.

Examples

Example 1

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

        3
       / \
      9  20
        /  \
       15   7

Output: True

At every node the left/right heights differ by at most 1.

Example 2

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

            1
           / \
          2   2
         / \
        3   3
       / \
      4   4

Output: False

At the left child 2, the left subtree has height 2 but the right subtree has height 1 below it — and at the root, left height 3 vs right height 1 breaks the rule.

Example 3

Input:  root = []
Output: True

An empty tree is balanced by definition.

Constraints

• The number of nodes is in [0, 5000] — O(n) is expected; O(n^2) squeaks by but is the “brute force” an interviewer will ask you to beat.
• -10^4 <= Node.val <= 10^4 — values are irrelevant; only the shape matters.

Think about it first

TL;DR

Bottom-up post-order DFS returning height or a -1 “unbalanced” sentinel — O(n) time, O(h) space.

Approach 1 — Brute force: top-down height checks

The naive intuition: for each node, compute the height of its left and right subtrees, compare them, then recurse into both children to check that they are balanced too.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import Optional


class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def height(node: Optional[TreeNode]) -> int:
            if not node:
                return 0
            return 1 + max(height(node.left), height(node.right))

        if not root:
            return True
        if abs(height(root.left) - height(root.right)) > 1:
            return False
        return self.isBalanced(root.left) and self.isBalanced(root.right)

Complexity: O(n^2) time in the worst case (a skewed tree recomputes each height once per ancestor; on balanced trees it’s O(n log n)), O(h) space. With n = 5000 a skewed tree costs ~12.5M height steps — it passes, but the redundancy is exactly what the follow-up targets.

Approach 2 — Bottom-up DFS with a sentinel (one pass)

The insight: the brute force computes heights and checks balance in two separate recursions over the same nodes. A post-order DFS — the classical traversal that processes both children before the node itself — already has both child heights in hand when it visits a node, so it can check balance and return the height in one visit. Encode “unbalanced somewhere below” as the impossible height -1 so failure short-circuits up the call stack.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import Optional


class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def check(node: Optional[TreeNode]) -> int:
            """Return subtree height, or -1 if unbalanced anywhere within."""
            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

Walkthrough on [1,2,2,3,3,null,null,4,4] (example 2): post-order reaches the 4 leaves first, each returning height 1. Their parent (left 3) gets left=1, right=1 → returns 2. The right 3 is a leaf → 1. Node 2 (left child of root) gets left=2, right=1 → |2-1| ≤ 1, returns 3… but wait — its left subtree 3→4,4 has height 2 and its right child 3 has height 1, difference 1, still fine; the failure appears at the root: left=3 (from the tall 2) vs right=1 (the childless 2), |3-1| = 2 > 1 → root returns -1 → answer False. Note how heights were each computed exactly once.

Complexity: O(n) time — every node is visited once. O(h) space for the recursion stack (O(n) worst case on a skewed tree).

Approach 3 — Iterative post-order (no recursion)

The insight: the same bottom-up computation works with an explicit stack if you defer a node until both children’s heights are known; a hash map stores heights of finished subtrees. Worth knowing for “do it without recursion” follow-ups or very deep trees that would blow Python’s recursion limit.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import Optional, Dict


class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        heights: Dict[Optional[TreeNode], int] = {None: 0}
        stack = [(root, False)] if root else []
        while stack:
            node, visited = stack.pop()
            if visited:
                left = heights[node.left]
                right = heights[node.right]
                if abs(left - right) > 1:
                    return False
                heights[node] = 1 + max(left, right)
            else:
                stack.append((node, True))
                if node.left:
                    stack.append((node.left, False))
                if node.right:
                    stack.append((node.right, False))
        return True

Walkthrough on [3,9,20,null,null,15,7] (example 1): the stack drills down to leaves 9, 15, 7, recording height 1 for each; 20 re-emerges with both children done → 1 + max(1,1) = 2; finally 3 sees left=1, right=2, difference 1 → never returns False, so the answer is True.

Complexity: O(n) time, O(n) space (stack plus the heights map).

Common pitfalls

• Checking balance only at the root — [1,2,2,3,null,null,3,4,null,null,4] is unbalanced even though the root’s two subtrees have equal height.
• Forgetting the empty-tree case: root = None must return True.
• In the sentinel version, computing 1 + max(left, right) before testing for -1 — the sentinel must propagate unchanged, or -1 becomes a legal-looking height.
• Confusing this with a complete or perfect tree check; height-balanced only bounds the per-node height gap by 1.

Pattern takeaway

When a tree question asks a global yes/no that depends on a per-subtree metric (height, size, sum), compute the metric bottom-up with post-order DFS and piggyback the check on the same return value — a sentinel like -1 turns “compute + validate” into one O(n) pass. Recomputing subtree metrics top-down is the classic O(n^2) trap.