559 · Maximum Depth of N-ary Tree

The binary version's recurrence — one plus the deeper child — generalises to "one plus the deepest of however many children there are." The recursion doesn't get more complicated; it just maxes over a list instead of comparing two numbers.

1 — The problem

Return the number of nodes along the longest path from the root down to any leaf. For a binary tree this is 1 + max(depth(left), depth(right)), with the convention depth(null) = 0. For an N-ary tree, "compare two children" becomes "take the max over a whole list of children" — and a node's children list, unlike a binary node's two slots, is simply empty when there are none, so there's no null-child edge case to special-case at all.

2 — Visualizing the recursion

Every frame below shows the DFS call stack as it grows down toward a leaf and unwinds back up, computing each node's depth the moment all of its children have reported theirs.

int maxDepth(Node nd) {    if (nd == null) return 0;    if (nd.children.isEmpty()) return 1;    int best = 0;    for (Node child : nd.children) {        best = Math.max(best, maxDepth(child));    }    return 1 + best;}

Node 3 is a leaf and returns 1 immediately. Node 1, the root, has to wait for all three of its children — 2, 3 and 4 — to report their own depths before it can take the max and add one; watch its frame stay open on the call stack for the entire rest of the traversal, exactly the way a binary root would wait on both of its subtrees.

3 — Complexity, edge cases, and the BFS alternative

• Time: O(n) — every node's depth is computed exactly once.
• Space: O(h) call stack, where h is the answer itself (the maximum depth) in the worst case.
• Empty tree: depth 0.
• Single node: depth 1, matching the children.isEmpty() base case directly.
• A very bushy, shallow tree (many children, few levels) makes the time cost come from breadth, not depth — still O(n) overall, but the recursion stack stays shallow throughout, unlike a narrow, deep chain where it's the stack itself that grows large.
• BFS alternative: exactly the level-order technique from 429, just counting how many times the outer while loop runs instead of collecting each level's values — useful if recursion depth is a genuine concern (a pathologically deep, narrow tree could exhaust the call stack before it exhausts memory).

4 — Reference implementation

public int maxDepth(Node root) {
    if (root == null) return 0;
    if (root.children.isEmpty()) return 1;
    int best = 0;
    for (Node child : root.children) {
        best = Math.max(best, maxDepth(child));
    }
    return 1 + best;
}

Alternatively, root.children.stream().mapToInt(this::maxDepth).max().orElse(0) + 1 collapses the loop into one expression once the base cases are out of the way — equivalent, marginally less obvious to a reader mid-interview.