roadmap/trees/Balanced Binary Tree

Balanced Binary Tree

EasyAmazonGoogleMicrosoftFacebook

Problem

Given a binary tree, determine if it is height-balanced (depth of subtrees never differs by more than 1 for any node).

Intuition — the key insight

The naive approach checks balance at each node separately, recomputing heights — O(n²). The optimal approach: combine height calculation and balance checking in one DFS. Return -1 from any subtree that's already unbalanced, propagating the unbalanced signal upward.

Approach

DFS returning height or -1

dfs(node) returns the height of the subtree if balanced, or -1 if unbalanced. If either child returns -1, propagate -1 upward. If heights differ by > 1, return -1. Otherwise return 1 + max(leftH, rightH).

Complexity

Time

O(n)

Space

O(h)

Visit each node once. Stack depth = tree height.

Solution code

Python

def isBalanced(self, root: TreeNode) -> bool:
    def dfs(node) -> int:
        if not node: return 0
        
        left  = dfs(node.left)
        right = dfs(node.right)
        
        if left == -1 or right == -1: return -1  # propagate unbalanced
        if abs(left - right) > 1:    return -1  # this node unbalanced
        
        return 1 + max(left, right)
    
    return dfs(root) != -1

Edge cases to remember

⚠Empty tree: balanced (return true)

⚠Single node: balanced

⚠The -1 sentinel avoids recomputing heights

Hints

What pattern do you think this problem uses?