Maximum Depth of Binary Tree

1. Problem & Core Objective

Return the maximum depth — the number of nodes along the longest path from the root down to a leaf.

      3
     / \
    9  20          →  3
       / \
      15  7

Constraints: 0 <= nodes <= 10^4 · -100 <= Node.val <= 100

What's actually being tested: the second half of the recursive contract — this time the call returns a value that the parent combines. Question 1 returned the node itself; here the return type carries information upward, which is the shape of nearly every remaining question in this section.

2. First-Principles Thought Process

Depth in terms of subtrees

The longest root-to-leaf path goes through one of the root's two children. So:

depth(node) = 1 + max(depth(left), depth(right))

The 1 counts the node itself; the max picks the deeper side.

The base case fixes the units

depth(null) = 0. An empty tree has no nodes, so its depth is zero — and a leaf then computes 1 + max(0, 0) = 1, which is correct for "number of nodes on the path".

This is where off-by-one errors live. LeetCode 104 counts nodes, so a single node has depth 1. Other problems count edges, where a single node has depth 0. The only difference is whether null returns 0 or −1, and the problem statement decides it. Always read which is meant.

Why this generalizes

1 + max(L, R) is the first instance of the pattern that runs through this whole section:

result(node) = combine(node.val, result(left), result(right))

Change combine and you get a different problem:

Getting comfortable here is what makes Q3 and Q14 tractable.

3. Solution Paths

Approach 1 — BFS counting levels

public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    Queue<TreeNode> q = new ArrayDeque<>();
    q.offer(root);
    int depth = 0;

    while (!q.isEmpty()) {
        int size = q.size();                    // snapshot this level
        for (int i = 0; i < size; i++) {
            TreeNode n = q.poll();
            if (n.left  != null) q.offer(n.left);
            if (n.right != null) q.offer(n.right);
        }
        depth++;                                 // one whole level done
    }
    return depth;
}

Count how many levels the BFS gets through.

• Time O(n) · Space O(w) — the widest level

Counter-questions on this approach

⭐ "Why the int size = q.size() snapshot?"

To separate the levels. Inside the loop I enqueue children, so q.size() is growing as I iterate. Capturing it first fixes how many nodes belong to the current level, so depth++ happens exactly once per level.

Without the snapshot the loop drains the queue completely and depth ends up as 1. It's the single most important line in every BFS-by-level problem, and it reappears in questions 8 and 9.

"Is O(w) better or worse than the recursion's O(h)?"

It depends entirely on the tree's shape, and neither dominates. A degenerate tree — effectively a linked list — has h = n and w = 1, so BFS wins hugely. A perfect tree has h = log n and w = n/2, so recursion wins. With n = 10^4, a degenerate tree gives 10,000 stack frames, which is where recursion becomes a real risk.

"Could you avoid the inner loop by storing depths in the queue?"

Yes — enqueue (node, depth) pairs and track the maximum. That removes the level-snapshot subtlety but allocates a wrapper per node. Both are fine; the snapshot version is more idiomatic and is what questions 8 and 9 need anyway.

Approach 2 — Recursion (optimal in clarity)

public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

Trace — [3,9,20,null,null,15,7]:

• Time O(n) · Space O(h) stack

Counter-questions on this approach

⭐ "Why does null return 0 rather than −1?"

Because this problem counts nodes, not edges. With null → 0, a leaf gets 1 + max(0,0) = 1, which is right for "one node on the path".

If the problem counted edges, a leaf should be 0 and null would return −1. The entire difference between the two conventions is that one base case, which is why I'd confirm which is meant before writing anything.

⭐ "Is there any risk with n = 10^4?"

Yes, on a degenerate tree. A left-leaning chain of 10,000 nodes means 10,000 stack frames. Java's default thread stack is around 512KB–1MB, which typically handles this but is not far off. If the constraint were 10^5 I'd switch to the BFS version, or to an explicit stack.

"Can this be done in O(1) space?"

Not without mutating the tree. You need to remember where to return to, which is inherently O(h). Morris traversal achieves O(1) by temporarily threading the tree, but it's an inorder technique and awkward for depth. O(h) is the honest floor.

"Does the order of the two recursive calls matter?"

No — Math.max is commutative and neither call has side effects. Unlike question 1 where independence was a property worth noting, here it's simply because the function is pure.

Comparison

(There's no meaningful "brute force" here — you must visit every node either way. The choice is which resource to spend.)

4. Why the Optimal Wins

Both are O(n) time, and neither dominates on space — it's O(h) against O(w), and which is smaller depends on the tree.

The recursion wins on clarity: three lines that restate the definition of depth directly. It's the right default, and I'd switch to BFS only when told the tree may be 10^5 nodes deep.

The framing worth keeping:

result(node) = combine(node, result(left), result(right)), with the base case at null fixing the units.

Every remaining question in this section is a choice of combine — and the ones that feel hard (Diameter, Max Path Sum) are hard only because combine produces two different quantities.

5. Java Prerequisites

The value-returning recursion

if (node == null) return identity;             // 0 for counting, -1 for edges,
int L = solve(node.left), R = solve(node.right);   // Integer.MIN_VALUE for maxima
return combine(node.val, L, R);

Math.max / Math.min take exactly two arguments; for three, nest them.

BFS level snapshot — the line that separates levels:

int size = q.size();                 // BEFORE enqueuing any children
for (int i = 0; i < size; i++) { ... }

ArrayDeque over LinkedList for queues — faster, less memory. It forbids null elements, which is fine since you never enqueue null.

6. Interview Communication Guide

Clarifying questions: Does depth count nodes or edges (nodes here — a single node is depth 1; confirm, it's the whole off-by-one)? Can the root be null (yes, returns 0)? How deep could the tree get (it decides recursion vs BFS)?

The pitch

"The longest root-to-leaf path goes through one of the two children, so the depth of a node is 1 + max(depth of left, depth of right) — the 1 for the node itself, the max for the deeper side.

The base case is null returning 0, and that's where I'd be careful: this problem counts nodes, so a leaf must come out as 1, which 1 + max(0,0) gives. If it counted edges, null would return −1 instead. That one base case is the entire difference between the two conventions, so I'd confirm which is meant.

O(n) time — every node is visited once — and O(h) stack space.

One caveat: at n = 10^4, a degenerate tree gives 10,000 stack frames, which is close to Java's default limit. If depth were a concern I'd do BFS by level instead, counting levels as I go, which is O(w) rather than O(h)."

Edge cases to volunteer:

Name [1]. It's the cheapest possible check of whether you got the node/edge convention right, and it distinguishes the two possible base cases immediately.

7. Follow-Up Questions — Modified Constraints

⭐ "Find the MINIMUM depth instead."

Not simply 1 + min(L, R) — that's the classic trap. For a node with one child, the null side returns 0 and min picks it, reporting a path that ends at a non-leaf. Minimum depth means the nearest leaf, so you must handle it explicitly:

Java

if (node.left == null)  return 1 + minDepth(node.right);
if (node.right == null) return 1 + minDepth(node.left);
return 1 + Math.min(minDepth(node.left), minDepth(node.right));

Worth knowing that max and min are not symmetric here — an asymmetry that surprises people.

⭐ "Check whether the tree is balanced."

Question 4 in this section. Naively you'd compute the height at every node and compare, but that re-walks the tree and is O(n²). The fix is to return height and balance from a single traversal, using a sentinel value like −1 to mean "already unbalanced".

"Return the deepest leaf's value, not the depth."

Return a pair — depth and value — or track a maximum in a field while recursing. Same traversal, richer return type. This is the first step toward the return-vs-record split in question 3.

"Compute the depth of an n-ary tree."

1 + max over all children, with an empty children list giving 1. Still O(n), since every child appears in exactly one parent's list.

"What if the tree could have 10^6 nodes in a single chain?"

Recursion is out — that's a guaranteed StackOverflowError. Use BFS by level, which is O(w) = O(1) for a chain, or an explicit stack, which moves the frames onto the heap where you control the size.

"What if the tree were stored on disk, a node at a time?"

BFS by level, because it reads nodes in the order they're likely laid out and needs only one level in memory. Recursion jumps around depth-first and would thrash. Same reasoning as external merge in the previous section — the algorithm is chosen by access pattern, not by complexity.