Given the root of a binary tree, return its maximum depth —
the number of nodes along the longest path from the root down to the farthest leaf node.
Input: root = [3,9,20,null,null,15,7]
Output: 3
Input: root = [1,null,2]
Output: 2
Constraints:
- 0 <= Number of nodes <= 104
- -100 <= Node.val <= 100
Contents
- Solution 1 — Recursive DFS
- Solution 2 — Iterative BFS
- Complexity Analysis
Recursive DFS
The depth of a tree is 1 + the maximum depth of its left and right subtrees.
This leads to a clean one-line recursive solution.
Algorithm:
- Base case: if root == null, depth is 0.
- Recursively compute depth of left and right subtrees.
- Return 1 + Math.max(leftDepth, rightDepth).
public int maxDepth(TreeNode root) {
if (root == null) return 0;
int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);
return 1 + Math.max(leftDepth, rightDepth);
}
Complexity:
- Time: O(n) — visits every node once.
- Space: O(h) — recursion stack depth equals tree height (O(log n) balanced, O(n) worst).
Iterative BFS (Level-Order)
Process the tree level by level with a queue. Each iteration of the outer loop
represents one complete level — count the levels.
public int maxDepth(TreeNode root) {
if (root == null) return 0;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int depth = 0;
while (!queue.isEmpty()) {
int levelSize = queue.size(); // nodes at current level
depth++;
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll();
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
}
return depth;
}
Complexity:
- Time: O(n) — every node is enqueued and dequeued exactly once.
- Space: O(n) — at most n/2 nodes in the queue at the widest level.
| Approach | Time | Space |
|---|
| Recursive DFS | O(n) | O(h) — call stack |
| Iterative BFS | O(n) | O(n) — queue |
For this problem both approaches are O(n) time. DFS is preferred for its simplicity and O(h) space on balanced trees.