We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

N-ary Tree Postorder Traversal

Difficulty: Easy

Problem Description

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

Key Insights

  • The postorder traversal visits the children of a node before visiting the node itself.
  • An n-ary tree is a tree in which each node can have an arbitrary number of children.
  • Recursive solutions are straightforward, but we can also implement an iterative solution using a stack.

Space and Time Complexity

Time Complexity: O(N) - where N is the number of nodes in the tree, as we must visit every node. Space Complexity: O(H) - where H is the height of the tree, for the recursive stack or the stack used in the iterative approach.

Solution

To solve the problem, we can use a depth-first search (DFS) approach. We can either implement it recursively or iteratively. For the iterative approach, we will use a stack to simulate the call stack used in recursion. We push the root onto the stack, and for each node, we push its children onto the stack. We reverse the output at the end to achieve the correct postorder result.

Code Solutions

def postorder(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]  # Reverse the result to get postorder
← Back to All Questions