A help portal stores nested articles as a binary tree: each article has at most two child articles. The left rail needs the deepest nesting so it can size the indent gutter. The intern version walked every root-to-leaf path, stuffed each leaf’s node count into a list, then took the max. A dozen articles painted instantly. A million-node imported taxonomy still walked everyone and kept a list of leaf depths a subtree return never needed.

Maximum depth is the number of nodes on the longest root-to-leaf path. A binary tree already gives left and right. Enumerating every root-to-leaf uses that and still copies work a subtree return already computed. DFS owns recursion versus an explicit stack. Here we only care about 1 + max(left, right). Do not stamp finish times or hunt back edges.

The problem

Given the root of a binary tree, return its maximum depth — the number of nodes along the longest path from the root down to a leaf. An empty tree is depth 0. A single node is depth 1.

final class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

Sample trees, counting nodes not edges:

      3
     / \
    9  20
      /  \
     15   7     →  3
[]              →  0
[1]             →  1

Note: Some definitions count edges on that path, which would make a lone node depth 0. This prompt counts nodes. Do not return 1 for null and do not return 0 for a leaf.

Walk every root-to-leaf is the honest brute force

From the root, record the node count on every path that ends at a leaf, then take the max. Correct. Extra: you materialize a list of leaf depths you never needed, and you think in “paths” instead of “this subtree’s height.”

int maxDepthCollect(TreeNode root) {
    if (root == null) {
        return 0;
    }
    List<Integer> leafDepths = new ArrayList<>();
    collect(root, 1, leafDepths);
    return Collections.max(leafDepths);
}

void collect(TreeNode node, int depth, List<Integer> leafDepths) {
    if (node.left == null && node.right == null) {
        leafDepths.add(depth);
        return;
    }
    if (node.left != null) {
        collect(node.left, depth + 1, leafDepths);
    }
    if (node.right != null) {
        collect(node.right, depth + 1, leafDepths);
    }
}

At a dozen nodes this is a rounding error. At a million-node spine you still visit everyone, plus a list of leaf depths you do not need. The intended answer never stores that list: a node’s depth is one plus the taller child.

One plus the taller child

Null returns 0. A node returns 1 + max(left, right). The leaves return 1 (both children null). The root’s answer is the longest node-count path because each call stacked one node on the deeper side.

maxDepth(9) = 1 + max(0, 0) = 1     maxDepth(15) = maxDepth(7) = 1
maxDepth(20) = 1 + max(1, 1) = 2
maxDepth(3)  = 1 + max(1, 2) = 3

The Java is that recurrence:

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

Time is O(n) — each node is visited once. Space is O(h) for the call stack, h being height. A spine of a million nodes is a million frames; the iterative version with an explicit stack is the same bound without blowing the JVM stack.

Level-count is a second correct procedure

Drain the tree a level at a time. Each drained level adds one to the depth. A null root returns 0 before you offer; the first level is the root, so a lone node returns 1.

int maxDepthLevels(TreeNode root) {
    if (root == null) {
        return 0;
    }
    Queue<TreeNode> q = new ArrayDeque<>();
    q.add(root);
    int depth = 0;
    while (!q.isEmpty()) {
        int n = q.size();
        for (int i = 0; i < n; i++) {
            TreeNode node = q.remove();
            if (node.left != null) {
                q.add(node.left);
            }
            if (node.right != null) {
                q.add(node.right);
            }
        }
        depth++;
    }
    return depth;
}

Same O(n) time. Extra space is the widest level, not the height. Prefer the recursive return at the board unless they ask for BFS; it is one idea (1 + max) instead of a queue plus a level counter.

What interviewers usually poke next

  • Edges vs nodes. If they switch to edge-count, a leaf is 0 and you still return 0 for null. Name the unit before you edit the + 1.
  • Diameter of Binary Tree. Longest node path between any two nodes, not necessarily through the root. Later sibling — do not compute diameters in maxDepth. Optional URL: /interview/trees/easy/diameter-of-binary-tree/.
  • Balanced Binary Tree. Every node has subtree depths differing by at most one. Later sibling. Optional URL: /interview/trees/easy/balanced-binary-tree/.
  • Million-node spine. Recursion depth is O(h). Say you would switch to an explicit stack or the level-count walk so the JVM does not blow the stack.

You are done with this problem when you can say empty is 0, a leaf is 1, and 1 + max(left, right) is the whole algorithm — not a list of root-to-leaf walks.