Balanced Binary Tree

Signal

Checking a global property ("is every subtree balanced") that depends on height at every node is a post-order job — but the naive version computes height and checks balance as two separate passes. The tell that you can do better: short-circuit the moment one subtree is already unbalanced instead of finishing the computation.

Approach

Write a post-order helper that returns the subtree's height if it's balanced, or a sentinel -1 the instant any descendant is found unbalanced — and once -1 appears, propagate it straight up without doing further work on that branch.

Skeleton

def height(node):
    if not node: return 0
    l = height(node.left)
    if l == -1: return -1
    r = height(node.right)
    if r == -1: return -1
    if abs(l - r) > 1: return -1
    return 1 + max(l, r)
return height(root) != -1

Solution

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


def is_balanced(root: TreeNode | None) -> bool:
    def height(node: TreeNode | None) -> int:
        if node is None:
            return 0
        left = height(node.left)
        if left == -1:
            return -1
        right = height(node.right)
        if right == -1:
            return -1
        if abs(left - right) > 1:
            return -1
        return 1 + max(left, right)

    return height(root) != -1

Complexity

O(n) time — the -1 short-circuit means each node is visited once. O(h) recursion stack space. The two-pass version (height, then a separate balance check per node) is O(n²) on a skewed tree.

Pitfalls

• Computing height and checking balance as two separate top-down passes is the common first instinct and quietly costs O(n²).
• -1 is a sentinel for already-unbalanced, not a legitimate height — don't let a real height of 0 (an empty subtree) get confused with it, and don't keep computing the sibling subtree once one side has already failed.