Balanced Binary Tree

Interview Prep

Warm-upTrees Variation of Maximum Depth of Binary Treetreesrecursion

The problem

A binary tree is height-balanced if, at every node, the heights of the two subtrees differ by at most one. Return whether the input tree is height-balanced. Empty trees are balanced. 

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

Naive: O(n²)

The straightforward implementation runs depth independently at every node, then recurses. Each depth call is O(size) and we do it at every node — quadratic total. Same trap as Diameter. 

def is_balanced_naive(root):
    """O(n^2): depth recomputed at every node."""
    if root is None: return True
    def depth(n):
        if n is None: return 0
        return 1 + max(depth(n.left), depth(n.right))
    if abs(depth(root.left) - depth(root.right)) > 1: return False
    return is_balanced_naive(root.left) and is_balanced_naive(root.right)

Pattern: fold the check into one post-order pass

Standard tree-DP trick: have the recursion return the depth of the current subtree, or a sentinel value (here -1) meaning "this subtree was already found to be unbalanced". Once either child returns the sentinel, propagate it up immediately without computing anything else.

This is "early exit through the return value" — a clean way to short-circuit a recursive check without raising exceptions or threading a boolean around. The same idiom shows up in many tree-validation problems (e.g., Validate BST with bounds).

Solution

def is_balanced(root: Node | None) -> bool:
    """O(n).  Post-order returns depth, or -1 as a sentinel for 'unbalanced below here'."""
    UNBALANCED = -1
    def check(node):
        if node is None:
            return 0
        l = check(node.left)
        if l == UNBALANCED: return UNBALANCED
        r = check(node.right)
        if r == UNBALANCED: return UNBALANCED
        if abs(l - r) > 1:  return UNBALANCED
        return 1 + max(l, r)
    return check(root) != UNBALANCED

Trace

Tree:        1
            / \
           2   2
          / \
         3   3
        / \
       4   4

check(leaf 4): returns 1.
check(3, left): l=1, r=0, |1-0|=1 ok, returns 2.
check(3, right): returns 1.
check(2, left): l=check(3,left)=2, r=check(3,right)=1, |2-1|=1 ok, returns 3.
check(2, right): returns 1.
check(1):
  l = check(2, left) = 3.
  r = check(2, right) = 1.
  |3 - 1| = 2 > 1 -> return UNBALANCED.

is_balanced(root) -> False

Complexity

Variants of "balanced"

The problem says "height-balanced" — the AVL-tree definition. Other definitions exist: