DSA problem
Maximum Depth of Binary Tree
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. For a tree consisting of a single root the depth is 1, and for an empty tree the depth is 0.
The most natural recursive solution is depth-first search: the depth of a tree equals one plus the maximum depth of its two subtrees. While this is concise and elegant, it implicitly uses the call stack, which on a degenerate (skewed) tree of n nodes can grow to O(n) frames. That is acceptable for most inputs, but level-order traversal gives us a clean iterative alternative.
To fit this category, we solve the problem with breadth-first search. We push the root into a queue and process the tree one level at a time. Each iteration of the outer loop corresponds to a single depth level: we record the current queue size, dequeue exactly that many nodes, and enqueue their non-null children. Incrementing a counter once per outer iteration directly produces the maximum depth.
This BFS formulation runs in O(n) time because every node is enqueued and dequeued exactly once, and O(w) space where w is the maximum width of the tree. For a balanced tree the width is roughly n / 2 at the deepest level, while for a skewed tree the width is 1 — making BFS strictly better than recursion in the worst case for skewed trees.
Examples
root = [3,9,20,null,null,15,7]3root = [1,null,2]2root = []0Constraints
- The number of nodes in the tree is in the range [0, 10^4].
- -100 <= Node.val <= 100
- The tree may be skewed; do not assume it is balanced.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.