N-ary Tree Postorder Traversal: Process Children Before Parents

Given the root of an n-ary tree, return the postorder traversal of its node values. Each node can have any number of children, and postorder means you visit every child subtree before visiting the node itself.

This is LeetCode 590: N-ary Tree Postorder Traversal. It extends the classic binary tree postorder to trees where each node may have more than two children. The same "children before parent" rule applies, just with a variable-length children list instead of fixed left and right pointers.

Example: given root = [1, null, 3, 2, 4, null, 5, 6], the postorder traversal is [5, 6, 3, 2, 4, 1].

Why this problem matters

Postorder traversal is the natural order for bottom-up processing. Whenever you need to compute a value for a node that depends on values already computed for its children, postorder is the traversal you want. Think of calculating directory sizes in a file system: you need the sizes of all subdirectories before you can total up the parent.

In an n-ary tree, this becomes even more relevant because each node may have many children. You cannot fall back on simple "go left, go right" logic. Instead, you iterate through the children list, which forces you to think about the traversal order more carefully.

Mastering this problem also reinforces a powerful trick: you can compute postorder iteratively by doing a modified preorder and reversing the result. This avoids the complexity of tracking which children have been fully processed, and it generalizes cleanly from binary trees to n-ary trees.

The approach

The iterative approach uses a clever observation. Normal preorder visits the root first, then its children left to right. If you record the root first and then push all children onto a stack (so the rightmost child gets processed next), you get a root-rightmost-first ordering. Reversing that gives you leftmost-children-first, then root last, which is exactly postorder.

def postorder(root):
    if not root:
        return []

    result = []
    stack = [root]

    while stack:
        node = stack.pop()
        result.append(node.val)
        stack.extend(node.children)

    return result[::-1]

Here is why this works:

• Pop and record: each node is popped from the stack and its value is appended to result. This records nodes in a modified preorder (root before children).
• Push children left to right: stack.extend(node.children) pushes children in order, so the last child ends up on top of the stack and gets popped first. This means the traversal visits the rightmost child before the leftmost.
• Reverse at the end: the modified preorder produces root, then rightmost subtree, then leftmost subtree. Reversing that yields leftmost subtree, rightmost subtree, then root, which is postorder.

Step-by-step walkthrough

Let's trace the iterative approach on the example tree where root 1 has children [3, 2, 4] and node 3 has children [5, 6]. The modified preorder collects [1, 4, 2, 3, 6, 5], and reversing gives the postorder [5, 6, 3, 2, 4, 1].

Notice how the stack processes nodes in the opposite order from what you might expect. Because children are pushed left to right, the rightmost child (4) gets popped first. This is intentional: the reversal at the end flips everything back into the correct postorder sequence.

Complexity analysis

Edge cases to watch for

• Empty tree (root is None): return an empty list. The early return handles this before the loop runs.
• Single node (no children): return [root.val]. The node is popped, recorded, and stack.extend([]) adds nothing. Reversing a single-element list returns itself.
• Deep chain (each node has one child): the stack never holds more than one node at a time. The modified preorder records nodes top to bottom, and reversal flips them to bottom-up postorder.
• Wide tree (root has many children): all children are pushed at once, so the stack can grow to O(n). This is the worst case for memory, but the algorithm still works correctly.
• All children are leaves: the root is recorded first, then each leaf is popped and recorded. Reversal puts all leaves before the root, which is correct postorder.

The building blocks

This problem builds on the "reversed modified preorder" pattern. The idea is simple: when a direct iterative postorder is awkward (because you need to know when all children are done), flip the problem. Do a traversal that is easy to implement iteratively (modified preorder), then reverse. You already know how to do iterative preorder with a stack, so the hard part disappears.

The second building block is generalizing from binary to n-ary trees. In a binary tree, you push node.left and node.right. In an n-ary tree, you push node.children. The rest of the logic is identical. If you have solved Binary Tree Postorder Traversal, adapting to n-ary is a one-line change. This kind of generalization, replacing two fixed children with a list, comes up frequently in tree problems involving file systems, DOM trees, and organizational hierarchies.

From understanding to recall

You now know how to perform postorder traversal on an n-ary tree without recursion. The algorithm is three lines of logic: pop a node, record it, push its children. Then reverse the result. The trick is recognizing that this modified preorder, when reversed, produces postorder.

Understanding the reversal trick is the easy part. Reproducing it under interview pressure is harder. You need to remember that stack.extend(node.children) pushes children in order so the last child gets popped first, and that the final result[::-1] is what converts the modified preorder into postorder. Spaced repetition drills this into muscle memory. After a few rounds of writing the solution from scratch, the push order and the reversal step become automatic.

Related posts

• N-ary Tree Level Order Traversal - BFS on the same tree structure, processing nodes level by level instead of depth-first
• Binary Tree Postorder Traversal - The binary tree version of this problem, using the same reversed modified preorder trick
• Binary Tree Preorder Traversal - The iterative preorder that forms the foundation of the reversal trick used here