LeetCode 590: N-ary Tree Postorder Traversal

Problem Restatement

We are given the root of an N-ary tree.

An N-ary tree is a tree where each node may have any number of children.

We need to return the postorder traversal of the tree’s node values. In postorder traversal, we visit:

1. All children from left to right.
2. The current node after its children.

The input may be empty. If the tree has no nodes, return an empty list. The number of nodes is in the range [0, 10^4], node values are between 0 and 10^4, and the tree height is at most 1000. The follow-up asks for an iterative solution. (leetcode.com, github.com)

Input and Output

The node structure is usually given as:

class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children

Example function shape:

def postorder(root: "Node") -> list[int]:
    ...

Examples

Example 1:

root = [1,null,3,2,4,null,5,6]

This represents:

        1
      / | \
     3  2  4
    / \
   5   6

Output:

[5, 6, 3, 2, 4, 1]

We first visit the children of 3, then 3, then 2, then 4, and finally the root 1.

Example 2:

root = []

Output:

[]

An empty tree has no nodes to visit.

First Thought: Recursive DFS

Postorder traversal is naturally recursive.

For each node:

1. Recursively visit every child from left to right.
2. Add the current node’s value to the answer.

This is the opposite order from preorder. In preorder, we append the node before its children. In postorder, we append the node after its children.

Key Insight

A postorder traversal processes descendants before ancestors.

For an N-ary tree, the rule is:

visit child subtree 1
visit child subtree 2
...
visit child subtree k
visit node

So the DFS function should delay appending node.val until after all recursive child calls finish.

Algorithm

1. Create an empty result list.
2. Define a DFS function.
3. If the current node is None, stop.
4. For each child in node.children, recursively call DFS.
5. Append the current node’s value.
6. Return the result list.

Correctness

The algorithm visits every child subtree of a node before appending the node’s own value. This matches the definition of postorder traversal.

For each child, the same rule is applied recursively. Therefore, all descendants of that child are also visited before the child itself. Since children are processed in the order they appear in node.children, the traversal respects the required left-to-right child order.

The base case handles an empty node by adding nothing, which is correct for an empty subtree.

Therefore, the result list contains exactly the postorder traversal of the N-ary tree.

Complexity

Let:

n = number of nodes in the tree
h = height of the tree

The output list uses O(n) space.

Implementation

"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""

class Solution:
    def postorder(self, root: "Node") -> list[int]:
        result = []

        def dfs(node: "Node") -> None:
            if node is None:
                return

            for child in node.children:
                dfs(child)

            result.append(node.val)

        dfs(root)

        return result

Code Explanation

The result list stores the traversal:

result = []

The helper function traverses one subtree:

def dfs(node):

The empty tree case is:

if node is None:
    return

For postorder, we visit all children first:

for child in node.children:
    dfs(child)

Only after all children are processed do we append the current node:

result.append(node.val)

Finally, we start traversal from the root:

dfs(root)

Iterative Implementation

The follow-up asks for an iterative solution.

One clean approach is to use a stack and build a reversed root-first traversal.

If we process nodes in this order:

node, children from left to right

and then reverse the final result, we get postorder.

To make this work with a stack, we push children in normal order. Since the stack is last-in, first-out, the rightmost child is processed first, and reversing the final list restores left-to-right postorder.

class Solution:
    def postorder(self, root: "Node") -> list[int]:
        if root is None:
            return []

        result = []
        stack = [root]

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

            for child in node.children:
                stack.append(child)

        return result[::-1]

For the tree:

        1
      / | \
     3  2  4
    / \
   5   6

the stack process creates:

[1, 4, 2, 3, 6, 5]

Reversing it gives:

[5, 6, 3, 2, 4, 1]

which is the required postorder traversal.

Testing

class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children or []

def run_tests():
    s = Solution()

    root = Node(1, [
        Node(3, [Node(5), Node(6)]),
        Node(2),
        Node(4),
    ])
    assert s.postorder(root) == [5, 6, 3, 2, 4, 1]

    assert s.postorder(None) == []

    single = Node(1)
    assert s.postorder(single) == [1]

    chain = Node(1, [Node(2, [Node(3)])])
    assert s.postorder(chain) == [3, 2, 1]

    wide = Node(1, [Node(2), Node(3), Node(4)])
    assert s.postorder(wide) == [2, 3, 4, 1]

    print("all tests passed")

run_tests()

Test meaning: