[Easy] 110. Balanced Binary Tree

Given a binary tree, determine if it is height-balanced. A height-balanced binary tree is one 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]
      3
     / \
    9  20
      /  \
     15   7
Output: true

Example 2:

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

Example 3:

Input: root = []
Output: true

Constraints

• The number of nodes is in [0, 5000]
• -10^4 <= Node.val <= 10^4

Common Approaches

Typical techniques for this pattern:

Approach	Time	Space	Notes
Recursive DFS (this problem)	O(n)	O(h) stack	Natural for trees and graphs
Iterative DFS (stack)	O(n)	O(n)	Avoid recursion depth limits
DFS with memoization	O(n)	O(n)	Overlapping subproblems on graphs
Backtracking DFS	O(2^n) typical	O(n)	Enumerate choices with pruning

Thinking Process

Naive: Top-Down – O(n^2)

For each node, compute the height of left and right subtrees separately, check the difference, then recurse on children. This recomputes heights repeatedly – O(n) per node, O(n^2) total.

Optimal: Bottom-Up with Early Termination – O(n)

Compute height bottom-up and return -1 as a sentinel the moment an imbalance is detected. This way:

• Each node is visited exactly once
• An imbalance anywhere propagates up immediately, short-circuiting the rest of the tree

The key insight is combining two tasks into one recursive function: compute height and detect imbalance, using -1 as the “not balanced” signal.

Approach: Bottom-Up DFS – O(n)

Input: root = [3,9,20,null,null,15,7]
Output: True
# Tree:    3
#         / \
#        9  20
#           /  \
#          15   7
# Heights at root: left=1, right=2 → diff=1 ✓

Solution Explanation

Approach: Recursive DFS (this problem)

Key idea: ### Naive: Top-Down – O(n^2)

How the code works:

• Each node is visited exactly once
• An imbalance anywhere propagates up immediately, short-circuiting the rest of the tree

Walkthrough — input root = [3,9,20,null,null,15,7], expected output true:

1. Initialize variables from the problem setup.
2. Apply the main loop / recursion until the condition is met.
3. Confirm the result matches the expected output.

   Why -1 Works as a Sentinel

Normal heights are always ≥ 0, so -1 is an impossible height value. Once any subtree returns -1, every ancestor immediately returns -1 without doing further work. This is the early termination that makes it O(n).

Common Mistakes

• Computing height and checking balance in separate passes (top-down O(n^2))
• Forgetting to check leftHeight == -1 before computing rightHeight (misses early termination)
• Confusing “balanced” with “perfect” or “complete” – balanced only requires height difference ≤ 1 at every node

Key Takeaways

• Sentinel return value (-1) to encode both height and validity in a single function is a clean pattern
• Bottom-up > top-down when you can avoid redundant computation
• This pattern generalizes: any tree property that depends on subtree properties can use bottom-up DFS with early exit

Related Problems

• 104. Maximum Depth of Binary Tree – height computation (base case for this problem)
• 543. Diameter of Binary Tree – same bottom-up pattern, track max path
• 124. Binary Tree Maximum Path Sum – bottom-up with global max

References

• LC 110: Balanced Binary Tree on LeetCode
• LeetCode Discuss — LC 110: Balanced Binary Tree
• LeetCode Editorial (may require premium)

Template Reference

• Trees