N-ary Tree Postorder Traversal

Difficulty: Easy | Acceptance: 81.10% | Paid: No Topics: Stack, Tree, Depth-First Search

Given the root of an n-ary tree, return the postorder traversal of its nodes’ values.

Nary-Tree input serialization is represented in their level order traversal where each group of children is separated by the null value (See examples).

Examples

Example 1:

Input: root = [1,null,3,2,4,null,5,6]
Output: [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]
Output: [2,6,14,11,7,3,12,8,4,13,9,10,5,1]

Constraints

The number of nodes in the tree is in the range [0, 10⁴].
0 <= Node.val <= 10⁴
The height of the n-ary tree is less than or equal to 1000.

Recursive Depth-First Search

Intuition Postorder traversal visits all children nodes before the current node. We can recursively traverse the list of children and append the current node’s value to the result list after the recursive calls return.

Steps

• If the root is null, return an empty list.
• Initialize an empty list to store the result.
• Iterate through each child of the current node.
• Recursively call the postorder function on each child and extend the result list.
• Append the current node’s value to the result list.
• Return the result list.

class Solution:
    def postorder(self, root: 'Node') -> list[int]:
        result = []
        self._helper(root, result)
        return result

    def _helper(self, node: 'Node', result: list[int]) -> None:
        if not node:
            return
        for child in node.children:
            self._helper(child, result)
        result.append(node.val)

Complexity

• Time: O(N), where N is the number of nodes in the tree. We visit every node exactly once.
• Space: O(N), in the worst case (unbalanced tree), the recursion stack can grow as deep as the number of nodes.
• Notes: This is the most intuitive approach but may cause a stack overflow for extremely deep trees.

Iterative Depth-First Search using Stack

Intuition To simulate recursion iteratively, we use a stack. A common trick for postorder is to perform a “modified preorder” traversal (Root -> Right -> Left) and then reverse the result. This yields the correct Left -> Right -> Root order required for postorder.

Steps

• Initialize a stack and push the root node onto it.
• Initialize an empty list to store the result.
• While the stack is not empty:
  • Pop the top node from the stack.
  • Append the node’s value to the result list.
  • Push all of the node’s children onto the stack in their original order (left to right). Since the stack is LIFO, pushing left-to-right ensures the rightmost child is processed next (Root -> Right -> Left).
• After the loop, reverse the result list.
• Return the reversed list.

class Solution:
    def postorder(self, root: 'Node') -> list[int]:
        if not root:
            return []
        
        stack = [root]
        result = []
        
        while stack:
            node = stack.pop()
            result.append(node.val)
            # Push children in original order so rightmost is processed first
            for child in node.children:
                stack.append(child)
                
        return result[::-1]

Complexity

• Time: O(N), we visit each node once.
• Space: O(N), to store the stack and the result list.
• Notes: This approach avoids recursion depth limits. The Java example uses LinkedList.addFirst to effectively reverse the list during insertion, saving a separate reversal pass.