Balanced Binary Tree

Check whether the child heights at every node differ by at most one.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Balanced Binary Tree: A postorder height function returns a nonnegative height for a balanced subtree and -1 as a failure sentinel that ancestors propagate immediately.

Input and goalCheck whether the child heights at every node differ by at most one.

Start bottom-up height evaluationFor tree [1,2,5,3,null,6,7,4], call height(1), then descend its left chain 1 -> 2 -> 3 -> 4 before evaluating any right sibling.

• 1stack start
  • 2stack
    • 3stack
      • 4current
  • 5
    • 6
    • 7

callStack[1,2,3,4]untouchedRightSubtree5 with children 6,7

Recognize it

Use a sentinel summary when a parent needs a normal child aggregate but any descendant failure should abort remaining work, as in balanced-height checks or invalid-subtree detection.

Keep true

height(node) returns the exact nonnegative subtree height if every node below is balanced; otherwise it returns -1. Thus ancestors can distinguish valid data from failure without a second traversal.

Reuse it

Fuse a subtree summary with validation by reserving an impossible summary value for failure, then check it before doing more recursion; this generalizes to BST validation and parse-tree error propagation.

Pattern: Bottom-up tree DFS with an error value.

Simple idea: Return the subtree height when it is balanced. Return -1 when it is not. Once a child returns -1, pass it upward without more work.

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 < 0:
         return -1

      right = height(node.right)
      if right < 0 or abs(left - right) > 1:
         return -1
      return 1 + max(left, right)

   return height(root) >= 0

Cost: $O(n)$ time and $O(h)$ call-stack space.

The platform supplies TreeNode with val, left, and right; this snippet assumes that definition.