Balanced Binary Tree

Problem

Given a binary tree, determine if it is height-balanced.

Examples

The brute-force approach

For each node, compute the height of its left and right subtrees and check if they differ by more than 1. Recurse on all nodes.

def height(node):
    if not node: return 0
    return 1 + max(height(node.left), height(node.right))

def is_balanced(node):
    if not node: return True
    lh = height(node.left)
    rh = height(node.right)
    if abs(lh - rh) > 1: return False
    return is_balanced(node.left) and is_balanced(node.right)

O(n log n) — height is computed from scratch for each node, causing redundant work.

Spotting the pattern

This is a Tree Traversal problem. The key question to ask yourself:

If you're already computing the height of each subtree, what extra check can you add to detect imbalance in the same pass?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.