19. Maximum Depth of Binary Tree

Difficulty:EasyPattern:Tree DFS RecursionTime:O(n)Space:O(h)

Given the root of a binary tree, return its maximum depth.

Solves using Recursive Depth-First Search (DFS):

Base Case: If root === null, return 0.
Recursive Decomposition:
- Compute left subtree depth: leftDepth = maxDepth(root.left).
- Compute right subtree depth: rightDepth = maxDepth(root.right).
Return: Math.max(leftDepth, rightDepth) + 1 (adds $1$ for the current node level).

Recursively visiting each node processes the entire tree in linear $O(n)$ time while utilizing $O(h)$ call-stack space (where $h$ is tree height).

Example Walkthrough

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

Binary tree root.

Depth Calculation: Node 3 -> max(depth(9), depth(20)) + 1 = max(1, 2) + 1 = 3

Calculates depth bottom-up.

Output: 3

Maximum depth is 3.

Answer: Maximum binary tree depth calculation

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

💡 Recursively compute left and right subtree heights and return the maximum plus one.

Key Takeaways