104. Maximum Depth of Binary Tree

Problem

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

Explanation

First pass: BFS by levels

You can compute depth iteratively with a queue. Push the root, then repeatedly process the current level's nodes (captured by the queue size) and enqueue their children. Each full level processed increases the depth by one. This runs in O(n) time and O(n) space in the worst case.

Final pass: DFS recursion

The recursive definition is concise: the depth of a node is 1 + max(depth(left), depth(right)), with the base case being 0 for null. This visits each node once.

Time: O(n)
Space: O(h) where h is tree height (worst-case O(n) for a skewed tree)

Solution