104. Maximum Depth of Binary Tree
easyAsked at AppleMaximum Depth of Binary Tree is Apple's pure recursion warm-up. depth(node) = 1 + max(depth(left), depth(right)) with base case 0 on null. The interviewer wants you to also know the iterative BFS variant for environments where recursion depth is a concern.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Apple loops.
- Glassdoor (2026-Q1)— Apple SWE phone-screen reports list this as the canonical 10-minute tree recursion warm-up.
- Blind (2025-11)— Apple new-grad reports cite Maximum Depth as the recurring tree easy.
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.
Constraints
The number of nodes in the tree is in the range [0, 10^4].-100 <= Node.val <= 100
Examples
Example 1
root = [3,9,20,null,null,15,7]3Example 2
root = [1,null,2]2Approaches
1. Recursive DFS (optimal canonical)
depth(null) = 0; depth(node) = 1 + max(depth(left), depth(right)).
- Time
- O(n)
- Space
- O(h) recursion stack
function maxDepth(root) {
if (!root) return 0;
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}Tradeoff: One line, O(n) time. The recursion stack is O(h) — O(log n) for a balanced tree, O(n) for a degenerate one. Apple's preferred answer for clarity.
2. Iterative BFS with level count
Standard level-order BFS; count levels.
- Time
- O(n)
- Space
- O(w) max width of tree
function maxDepth(root) {
if (!root) return 0;
let queue = [root];
let depth = 0;
while (queue.length) {
const size = queue.length;
for (let i = 0; i < size; i++) {
const node = queue.shift();
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
depth++;
}
return depth;
}Tradeoff: Same complexity but the queue holds up to a level's worth of nodes, which can be larger than the height. Useful when recursion depth is a concern; Apple mentions this when the tree could be very tall.
3. Iterative DFS with explicit stack
DFS using a stack of (node, depth) pairs; track max depth seen.
- Time
- O(n)
- Space
- O(h)
function maxDepth(root) {
if (!root) return 0;
const stack = [[root, 1]];
let best = 0;
while (stack.length) {
const [node, d] = stack.pop();
best = Math.max(best, d);
if (node.left) stack.push([node.left, d + 1]);
if (node.right) stack.push([node.right, d + 1]);
}
return best;
}Tradeoff: Same O(n) time, O(h) space, no recursion. Apple sometimes asks for this version when discussing 'what if the tree could be 10^6 deep.'
Apple-specific tips
Apple is grading whether the recursion feels natural to you. Write the one-liner first; if asked 'how would you handle a tree so deep recursion would blow the stack?', switch to iterative DFS with an explicit stack. Both versions in your back pocket signal seniority.
Common mistakes
- Returning depth-in-edges instead of depth-in-nodes (off by one — the problem asks for nodes).
- Returning 1 (instead of 0) on null — produces depth 1 for an empty tree.
- Using BFS but forgetting to read queue.length BEFORE the inner loop — runs forever.
Follow-up questions
An interviewer at Apple may pivot to one of these next:
- Minimum Depth of Binary Tree (LC 111) — careful: must reach a LEAF (no children), not the first null.
- Balanced Binary Tree (LC 110) — check whether |left-depth - right-depth| <= 1 everywhere.
- Diameter of Binary Tree (LC 543) — uses depth as a subroutine with a side-effected best.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Is the empty tree depth 0?
Yes by convention — the recursion's null base case returns 0 and the problem accepts that.
When would you NOT use recursion?
When the tree could be deeper than the language's recursion limit (~10^4 in JS, ~10^3 in Python). The iterative DFS version handles arbitrary depth.
Free learning resources
Curated free links for this problem.