Balanced Binary Tree

Problem Statement

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

A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

Examples

Example 1

Input: root = [3,9,20,null,null,15,7]
Output: true

Tree:
      3
     / \
    9  20
      /  \
     15   7

Node 3: |height(left) - height(right)| = |1 - 2| = 1 ✓
Node 9: leaf ✓
Node 20: |1 - 1| = 0 ✓
All nodes balanced → tree is balanced

Example 2

Input: root = [1,2,2,3,3,null,null,4,4]
Output: false

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

Node 2: |height(left) - height(right)| = |3 - 1| = 2 ✗
Tree is NOT balanced

Example 3

Input: root = []
Output: true

Intuition

A tree is balanced if:

1. Left subtree is balanced
2. Right subtree is balanced
3. Height difference between left and right ≤ 1

This naturally fits a recursive pattern where we check balance bottom-up.

Pattern Recognition

This is a Tree DFS + Height Calculation problem with:

• Post-order traversal (check children before parent)
• Combine two checks: balance status + height
• Early termination on imbalance

Approach

Optimized: Single Pass DFS

Return two pieces of information from each recursive call:

1. Is subtree balanced?
2. Height of subtree

We can encode this efficiently:

• Return actual height if balanced
• Return -1 if unbalanced (sentinel value)

Algorithm:

1. Base Case: Null node is balanced with height 0
2. Recursive Case:
   • Get left subtree height (or -1 if unbalanced)
   • Get right subtree height (or -1 if unbalanced)
   • If either is -1 → return -1 (propagate imbalance)
   • If |left_height - right_height| > 1 → return -1
   • Otherwise → return 1 + max(left_height, right_height)

Why this works:

• Single pass through tree
• Early termination on first imbalance
• Height calculation is needed anyway

Naive Approach

Calculate height at each node and check difference:

isBalanced(root):
  if not root: return True
  left_height = height(root.left)
  right_height = height(root.right)
  return abs(left_height - right_height) <= 1 and
         isBalanced(root.left) and isBalanced(root.right)

Problem: O(n²) time - recalculates heights

Edge Cases

• Empty tree → balanced
• Single node → balanced
• Skewed tree → unbalanced
• Perfect tree → balanced
• Imbalance at any level

Complexity Analysis

• Time: O(n) where n = number of nodes

  • Visit each node once
  • O(1) work per node

• Space: O(h) where h = height

  • Recursion call stack
  • O(log n) for balanced, O(n) for skewed