590 · N-ary Tree Postorder Traversal

One line moves. In 589 the visit happens before the loop over children; here it happens after, so a node is recorded only once every subtree beneath it is finished. That is the property every aggregation problem in Pattern 2 depends on, which is the real reason to be fluent in it.

1 — The problem

Return the postorder traversal of an N-ary tree's values: for each node, all of its children (left to right) before the node itself. On LeetCode's [1,null,3,2,4,null,5,6] — root 1 with children 3, 2, 4, and 3 with children 5 and 6 — the answer is [5,6,3,2,4,1]. The root is always last.

2 — Recursive

void dfs(Node nd, List<Integer> out) {    if (nd == null) return;    for (Node c : nd.children) dfs(c, out);    out.add(nd.val);                  // visit on the way OUT}

Compare the shape of this run with 589's. The call stack behaves identically — the same frames open and close in the same order — but the output list fills in a completely different sequence, because the write now happens at the bottom of the function instead of the top. The traversal is not what changed; only the moment of recording is.

This is also why postorder is the only order that can aggregate from below: by the time a node records itself, every one of its descendants has already reported. Any problem phrased as "compute something for each node from its children's results" is postorder whether or not it says so.

3 — Iterative, without waiting

A true iterative postorder needs to know whether a node's children have been processed, which means either a visited flag or a lookahead. There is a shortcut that avoids both: run a preorder that pushes children in natural order — the mirror of 589 — and write each node to the front of the output.

Deque<Node> st = new ArrayDeque<>();st.push(root);while (!st.isEmpty()) {    Node nd = st.pop();    out.addFirst(nd.val);             // write to the FRONT    for (Node c : nd.children)        st.push(c);                   // natural order, not reversed}

Read the trace and you can see why it works. Popping in that order produces 1, 4, 2, 3, 6, 5: root first, children right to left. That is exactly postorder reversed, so inserting at the front instead of the back un-reverses it. The same trick appears for binary trees as reverse preorder.

The honest caveat, and a good thing to say out loud in an interview: this produces the right list, not the right visit moments. Nodes are still touched root-first, so you cannot hang bottom-up computation off this loop the way you can off the recursion. When the question is "return the postorder list" it is ideal; when the question is "compute something from each node's children", it is the wrong tool.

4 — Complexity and edge cases

• Time: O(n) for both versions. addFirst on a LinkedList is O(1), so the trick costs nothing; building with add and calling Collections.reverse at the end is equally fine and equally O(n).
• Space: O(h) for the recursion; O(n) worst case for the explicit stack, since one node's children can all be pushed at once.
• Empty root: return an empty list before touching the stack.
• Declare the output as LinkedList, not List, or addFirst won't compile — the same gotcha as 107.

5 — Reference implementations

public List<Integer> postorder(Node root) {
    List<Integer> out = new ArrayList<>();
    dfs(root, out);
    return out;
}

private void dfs(Node nd, List<Integer> out) {
    if (nd == null) return;
    for (Node c : nd.children) dfs(c, out);
    out.add(nd.val);                        // visit on the way out
}

public List<Integer> postorder(Node root) {
    LinkedList<Integer> out = new LinkedList<>();  // NOT List — addFirst
    if (root == null) return out;
    Deque<Node> st = new ArrayDeque<>();
    st.push(root);
    while (!st.isEmpty()) {
        Node nd = st.pop();
        out.addFirst(nd.val);               // un-reverses as we go
        for (Node c : nd.children) {
            st.push(c);                     // natural order — mirror of 589
        }
    }
    return out;
}

Redundant once you have done 589 and 145 — which is why it is marked optional. Worth ten minutes only if the reverse-preorder trick above was new to you.