104 · Maximum Depth of Binary Tree

The atom of postorder aggregation. Every node asks its two children the same question, takes the better answer, adds one for itself, and hands the result up. Sub-variant A is this shape; the rest of Pattern 2 changes what gets combined, never how.

1 — The problem

Return the number of nodes along the longest path from the root down to the farthest leaf. The recursion writes itself once you name three things: the identity (what an empty tree returns), the combine (how two child answers become one), and the node's own contribution.

Three lines of code, and the whole of sub-variant A is a substitution table over those three rows. LC 110 replaces the combine with a balance check plus a sentinel; LC 543 keeps this exact return value and records something else on the side.

2 — Watching the values come back up

Step through it. The interesting thing to watch is not the descent — that part is mechanical — but the moment each node has both child answers in hand and collapses them into one number. Nothing is known about a node until after both of its subtrees have finished.

Node 20 is the one to study. When the walk first arrives there, nothing is known — it could be a leaf for all the recursion can see. It is only after 15 returns 1 and 7 returns 1 that 20 can say 2. The root then has 1 from the left and 2 from the right, takes the larger, adds itself, and answers 3.

2.1 Why the identity has to be 0

Look at node 9, a leaf. Both of its children are null and both return the identity, so the combine sees max(0, 0) = 0 and 9 returns 1 — correct, with no special case for leaves anywhere in the code. That is the whole reason to define the base case on null rather than on "is a leaf":

Guarding on null is right here, but it is not universally right: LC 111 (minimum depth) and LC 112 (path sum) are exactly the problems where a single-child node makes the null guard give a wrong answer, and the leaf test has to come back. Sub-variant E exists to separate those two ideas.

3 — Complexity and edge cases

• Time O(n) — every node is entered once and does O(1) work. Space O(h) for the call stack, which is O(log n) on a balanced tree and O(n) on a degenerate one. On LeetCode's constraint of 10⁴ nodes a straight-line tree is fine; at 10⁵ a recursive solution can blow the stack and you want the iterative BFS instead.
• Empty tree: root == null returns 0, handled by the same guard that handles missing children. No special case at the entry point.
• Single node: returns 1. If your version returns 0, you are counting edges, not nodes — a legitimate definition, and the one LC 543 uses. Read the problem statement for which one is wanted.
• Common bug: writing 1 + Math.max(maxDepth(nd.left), maxDepth(nd.right)) is correct but recomputes nothing — it is fine. Writing Math.max(1 + maxDepth(nd.left), maxDepth(nd.right)) is the real bug: the +1 has to apply to both branches, because the node is on every path through it.

4 — Reference implementation

public int maxDepth(TreeNode nd) {
    if (nd == null) return 0;      // identity
    int L = maxDepth(nd.left);
    int R = maxDepth(nd.right);
    return 1 + Math.max(L, R);       // own contribution + combine
}

The iterative alternative, for when the tree may be deep enough to overflow the stack — count the levels a BFS peels off:

public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    Deque<TreeNode> q = new ArrayDeque<>();
    q.add(root);
    int depth = 0;
    while (!q.isEmpty()) {
        for (int i = q.size(); i > 0; i--) {
            TreeNode nd = q.poll();
            if (nd.left  != null) q.add(nd.left);
            if (nd.right != null) q.add(nd.right);
        }
        depth++;
    }
    return depth;
}