LeetCode Solutions Blog

N-ary Tree Postorder Traversal

Number: 776

Difficulty: Easy

Paid? No

Problem Description

Given the root of an n-ary tree, return the postorder traversal of its nodes' values. In an n-ary tree, each node can have multiple children. The input serialization uses level order traversal with each group of children separated by a null value.

Key Insights

Postorder traversal means visiting all children before the parent.
Recursive implementation is straightforward, but the challenge is to implement it iteratively.
Use a stack to simulate the recursive call stack and a technique to reverse the order of processed nodes.

Space and Time Complexity

Time Complexity: O(n) - Every node is processed exactly once.
Space Complexity: O(n) - In the worst case, the stack and output list may store all nodes.

Solution

To achieve an iterative postorder traversal, we use a stack to simulate recursion.

Start by pushing the root node onto the stack.
Pop a node from the stack and add its value to the result list.
Push all its children onto the stack.
Because postorder requires children to be processed before their parent, the order in which nodes are added to the result and then reversed at the end gives the correct postorder sequence.
Finally, reverse the result list before returning it.

This approach uses a modified preorder-like traversal (root, then children) but then reverses the output to mimic postorder.

Code Solutions

# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children if children is not None else []

def postorder(root):
    # If the tree is empty, return an empty list.
    if root is None:
        return []
    
    # Initialize an empty stack and result list.
    stack = [root]
    result = []
    
    # Process nodes until the stack is empty.
    while stack:
        # Pop the last node from stack.
        node = stack.pop()
        # Append the node's value to the result list.
        result.append(node.val)
        # Push all children of the node onto the stack.
        # No need to reverse here because final result will be reversed.
        for child in node.children:
            stack.append(child)
    
    # Reverse the result list to get postorder traversal.
    return result[::-1]

# Example usage:
# Construct tree: 1, children: [3,2,4]; node 3's children: [5,6]
node5 = Node(5)
node6 = Node(6)
node3 = Node(3, [node5, node6])
node2 = Node(2)
node4 = Node(4)
root = Node(1, [node3, node2, node4])
print(postorder(root))  # Output: [5, 6, 3, 2, 4, 1]