Trees · LC #104

Maximum Depth of Binary Tree

Return the maximum depth of a binary tree - the number of nodes along the longest root-to-leaf path. Classic post-order DFS where each node contributes 1 to whichever subtree is deeper.

easyLC #104AMZ★★GOO★★META★★MSFT★★AAPL★★
Mark as done
Confidence
Ask GPTPractice

Statement

Problem & Approach

Problem statement, sample I/O, and key reasoning.

Given the root of a binary tree, return its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Sample I/O

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

Input:  [1,null,2]
Output: 2

Time: O(n) · Space: O(h)

Intuition

How to Think About It

Intuition

Recursion works because the depth of a node is simply 1 plus the maximum depth of its two subtrees. The problem decomposes perfectly - each call only needs answers from its children, making DFS a natural fit.

Core Concept

Post-order DFS: recurse into left and right children first, then combine. Base case: null node has depth 0. Recursive case: `1 + max(depth(left), depth(right))`. Alternatively BFS level-order counts levels as it expands outward.

When to use

Any problem asking for tree height, depth, or longest root-to-leaf distance. Also a building block for balance checks and diameter problems.

When NOT to use

Avoid deep recursion on pathologically unbalanced (skewed) trees where stack depth approaches n - prefer iterative BFS to avoid stack overflow.

Key Insights

What to Know Cold

  • Null node base case returns 0, so leaf nodes correctly return 1.
  • Post-order: children computed before parent - result flows upward.
  • Iterative BFS alternative: count how many levels the queue processes.
  • On a balanced tree h = O(log n); on a skewed tree h = O(n).
  • Same pattern used in diameter, balance check, and path sum problems.

1 example

Worked Examples

Complete-ish binary tree

Tree [3,9,20,null,null,15,7] - root has left leaf 9 and right subtree depth 2.

depth(3) = 1 + max(depth(9), depth(20)). depth(9)=1, depth(20)=1+max(1,1)=2. Result: 3.

function maxDepth(root: TreeNode | null): number {
  if (!root) return 0;
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

Output: 3

Demonstrates the one-liner recursive pattern that covers all tree shapes.