LeetCode 590 - N-ary Tree Postorder Traversal

Difficulty: 🟢 Easy
Topics: Stack, Tree, Depth-First Search

Solution

Problem Understanding

This problem asks us to perform a postorder traversal on an n-ary tree.

In a binary tree, each node has at most two children. In an n-ary tree, each node can have any number of children. Every node contains a value and a list of child nodes.

A postorder traversal means:

Visit all children first
Then visit the current node itself

For an n-ary tree, this means we recursively process each child from left to right, and only after all children are processed do we add the current node's value to the result.

For example, consider this tree:

The postorder traversal is:

5, 6, 3, 2, 4, 1

because we fully process node 3 and its subtree before visiting 3 itself, then process 2, then 4, and finally 1.

The input is provided as the root node of the tree. Internally, each node contains:

A value
A list of child nodes

The constraints tell us several important things:

The tree may contain up to 10^4 nodes, so the solution must be efficient.
The tree height can be as large as 1000, which means a recursive solution is acceptable in many languages, but recursion depth could become risky in some environments.
We should aim for linear time complexity because every node must be visited at least once.

Important edge cases include:

An empty tree where root == None
A tree with only one node
Deep trees with long chains of children
Nodes with empty child lists
Highly unbalanced trees

The problem also includes a follow-up asking for an iterative solution, which means we should understand how to simulate recursive depth-first traversal using an explicit stack.

Approaches

Brute Force Approach

The most straightforward solution is recursive depth-first traversal.

For every node:

Recursively traverse all children
Append the current node's value afterward

This directly matches the definition of postorder traversal, so it is easy to reason about and implement correctly.

The recursive approach visits every node exactly once, making it efficient enough for the given constraints. However, recursion relies on the call stack. In extremely deep trees, this can become problematic because recursion depth is limited in some programming environments.

Although this approach is already optimal in time complexity, the problem follow-up specifically asks whether we can solve it iteratively.

Optimal Approach

The iterative solution uses a stack to simulate recursion.

The key insight is that postorder traversal processes children before parents. One useful trick is:

Perform a modified preorder traversal
Process nodes in root-first order
Reverse the final result

For an n-ary tree:

Normal preorder is:

root -> children left to right

If we process:

root -> children right to left

and then reverse the result, we obtain:

children left to right -> root

which is exactly postorder traversal.

This works because reversing the traversal naturally delays parent processing until after all descendants are handled.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(h)	Recursive DFS using call stack
Optimal	O(n)	O(n)	Iterative traversal using explicit stack

Here:

n is the number of nodes
h is the tree height

Algorithm Walkthrough

Iterative Postorder Traversal

Initialize an empty result list.

This list will temporarily store nodes in modified preorder order. 2. Handle the empty tree case.

If the root is None, return an empty list immediately because there are no nodes to traverse. 3. Create a stack and push the root node onto it.

The stack simulates the recursive DFS call stack. 4. While the stack is not empty, continue processing.

This loop ensures every node is visited exactly once. 5. Pop the top node from the stack.

This becomes the current node being processed. 6. Append the current node's value to the result list.

At this stage, the order is not yet true postorder. 7. Push all children onto the stack.

Since stacks are LIFO structures, pushing children from left to right causes the rightmost child to be processed first.

This produces a traversal order similar to:

root -> right -> left

After all nodes are processed, reverse the result list.

Reversing transforms the traversal into proper postorder:

left -> right -> root

Return the reversed result.

Why it works

The algorithm processes nodes in a modified preorder sequence where parents are visited before children. Because the traversal order is effectively reversed afterward, every parent node appears after all of its descendants in the final output. This exactly matches the definition of postorder traversal.

Python Solution

"""
# Definition for a Node.
class Node:
    def __init__(self, val: Optional[int] = None, children: Optional[List['Node']] = None):
        self.val = val
        self.children = children
"""

from typing import List, Optional

class Solution:
    def postorder(self, root: 'Node') -> List[int]:
        if not root:
            return []

        result = []
        stack = [root]

        while stack:
            node = stack.pop()

            result.append(node.val)

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

        return result[::-1]

The implementation begins by handling the empty tree case. If the root is None, we immediately return an empty list.

We then initialize two structures:

result, which stores traversal values
stack, which controls DFS traversal order

The main loop continues until the stack becomes empty. During each iteration:

A node is removed from the stack
Its value is appended to result
All children are pushed onto the stack

Because stacks process the most recently added element first, children are explored in reverse order relative to insertion. This creates a reversed postorder sequence.

Finally, result[::-1] reverses the traversal and produces the correct postorder ordering.

Go Solution

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Children []*Node
 * }
 */

func postorder(root *Node) []int {
    if root == nil {
        return []int{}
    }

    result := []int{}
    stack := []*Node{root}

    for len(stack) > 0 {
        lastIndex := len(stack) - 1
        node := stack[lastIndex]
        stack = stack[:lastIndex]

        result = append(result, node.Val)

        for _, child := range node.Children {
            stack = append(stack, child)
        }
    }

    left := 0
    right := len(result) - 1

    for left < right {
        result[left], result[right] = result[right], result[left]
        left++
        right--
    }

    return result
}

The Go implementation follows the same algorithmic idea as the Python version.

Some Go-specific details are important:

nil is used instead of None
Slices are used for both the stack and result list
Since Go does not provide built-in slice reversal, we manually reverse the result using two pointers
Stack operations are implemented using slice append and slicing

The solution safely handles empty trees and arbitrary n-ary structures.

Worked Examples

Example 1

Input:

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

Tree:

Iteration Trace

Step	Stack	Current Node	Result Before Reverse
Initial	[1]	-	[]
1	[3,2,4]	1	[1]
2	[3,2]	4	[1,4]
3	[3]	2	[1,4,2]
4	[5,6]	3	[1,4,2,3]
5	[5]	6	[1,4,2,3,6]
6	[]	5	[1,4,2,3,6,5]

Reverse result:

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

Example 2

Input:

root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]

The traversal systematically explores all descendants before parents.

Important Intermediate States

Step	Current Node	Result Before Reverse
1	1	[1]
2	5	[1,5]
3	10	[1,5,10]
4	9	[1,5,10,9]
5	13	[1,5,10,9,13]
...	...	...

Final reversed result:

[2,6,14,11,7,3,12,8,4,13,9,10,5,1]

The reversal ensures that every parent node appears after all of its children.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Every node is visited exactly once
Space	O(n)	Stack and result list may store all nodes

The traversal processes each node a single time, so the total runtime is linear in the number of nodes.

The space complexity is also linear because:

The stack may contain many nodes simultaneously
The result list stores all node values

Even though recursion could use only O(h) auxiliary space, the iterative approach explicitly manages traversal state using a stack.

Test Cases

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

class Solution:
    def postorder(self, root):
        if not root:
            return []

        result = []
        stack = [root]

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

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

        return result[::-1]

solution = Solution()

# Empty tree
assert solution.postorder(None) == []  # tests null root

# Single node
root = Node(1)
assert solution.postorder(root) == [1]  # tests single-node tree

# Example 1
root = Node(1, [
    Node(3, [Node(5), Node(6)]),
    Node(2),
    Node(4)
])

assert solution.postorder(root) == [5, 6, 3, 2, 4, 1]  # provided example

# Linear chain
root = Node(1, [
    Node(2, [
        Node(3, [
            Node(4)
        ])
    ])
])

assert solution.postorder(root) == [4, 3, 2, 1]  # deep chain

# Wide tree
root = Node(1, [
    Node(2),
    Node(3),
    Node(4),
    Node(5),
    Node(6)
])

assert solution.postorder(root) == [2, 3, 4, 5, 6, 1]  # many siblings

# Mixed structure
root = Node(1, [
    Node(2, [Node(5), Node(6)]),
    Node(3),
    Node(4, [Node(7)])
])

assert solution.postorder(root) == [5, 6, 2, 3, 7, 4, 1]  # mixed branching

Test	Why
Empty tree	Validates handling of `None` input
Single node	Ensures simplest non-empty tree works
Example 1	Verifies correctness against provided example
Linear chain	Tests deep recursive-style structure
Wide tree	Tests nodes with many children
Mixed structure	Validates general traversal correctness

Edge Cases

Empty Tree

The tree may contain zero nodes, meaning root is None. This is a common source of bugs because attempting to access root.children would raise an error. The implementation avoids this by immediately returning an empty list when root is falsy.

Single Node Tree

A tree with only one node has no children. Some implementations accidentally skip processing leaf nodes or mishandle empty child lists. Here, the algorithm correctly pushes the root onto the stack, processes it, and returns [root.val].

Deeply Nested Tree

The tree height may reach 1000, creating very deep recursive call chains. Recursive solutions risk stack overflow in some languages or environments. The iterative solution avoids this issue entirely because it uses an explicit stack allocated on the heap instead of relying on recursive function calls.

Nodes With Empty Children Lists

Leaf nodes have empty children arrays. Some implementations assume every node has children and may iterate incorrectly over None. The provided solution safely handles empty child lists because iterating over an empty list naturally performs no operations.

Highly Unbalanced Trees

An n-ary tree can be extremely skewed, where one branch is much deeper than others. The algorithm still works correctly because DFS traversal naturally adapts to arbitrary tree shapes without relying on balancing assumptions.