Domain 1EasyCORE

N-ary Tree Postorder Traversal

The problem asks for the postorder traversal of an n-ary tree. In postorder traversal, we visit all the children of a node before visiting the node itself. The input is given as the root of the n-ary tree, and the output should be a list of node values in postorder.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Tree

590. N-ary Tree Postorder Traversal

Model: qwen2.5-coder:14b
Topics: Tree
FAANG asked: 1
Acceptance rate: 73.6%


Problem Breakdown

The problem asks for the postorder traversal of an n-ary tree. In postorder traversal, we visit all the children of a node before visiting the node itself. The input is given as the root of the n-ary tree, and the output should be a list of node values in postorder.

Inputs:

  • root: The root node of an n-ary tree.

Outputs:

  • A list of integers representing the postorder traversal of the tree’s nodes.

Implicit Constraints or Tricky Edge Cases:

  • The tree can be empty (root is None).
  • Nodes can have zero or more children.
  • The number of nodes is in the range [0, 10^4].

Intuition

A brute-force approach would involve recursively visiting each node and its children, which is straightforward but not optimal in terms of space complexity due to the call stack. The key insight for a better approach is to use an iterative method with a stack to simulate the recursive behavior without using additional function calls.

Approach

To achieve postorder traversal iteratively, we can use a stack to keep track of nodes. We start by pushing the root node onto the stack. Then, while the stack is not empty, we pop a node from the stack and add its value to the result list. Instead of immediately visiting the children, we push them onto the stack in reverse order (so that they are processed in the correct order). This way, when we pop nodes from the stack, we process them in postorder.

Complexity Analysis

  • Time Complexity: O(n), where n is the number of nodes in the tree. Each node is visited exactly once.
  • Space Complexity: O(n) due to the space required for the stack and the result list.

Solution

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

def postorder(root: 'Node') -> List[int]:
    if root is None:
        return []
    
    stack, result = [root], []
    
    while stack:
        node = stack.pop()
        result.append(node.val)
        # Add children to the stack in reverse order
        for child in reversed(node.children):
            stack.append(child)
    
    # Reverse the result list to get the correct postorder traversal
    return result[::-1]

Edge Cases Handled

  • Empty Tree: If root is None, the function returns an empty list.
  • Single Node Tree: If the tree has only one node, it will be returned as the sole element in the result list.
  • Nodes with No Children: Nodes without children are simply added to the result list when processed.