590. N-ary Tree Postorder Traversal

This problem asks for a postorder traversal of an N-ary tree. Postorder traversal means visiting the nodes in the order of: left subtree, right subtree, ..., root. In an N-ary tree, "left" and "right" generalize to all children.

Solutions

Two approaches are presented: recursion and iteration.

Solution 1: Recursion

This is the most straightforward approach for tree traversal. The recursive function dfs performs the following steps:

1. Base Case: If the node is null, it returns.
2. Recursive Calls: It recursively calls dfs on each of the node's children.
3. Append to Result: After processing all children, it appends the current node's value to the ans list.

Time Complexity: O(N), where N is the number of nodes in the tree. Each node is visited exactly once.

Space Complexity: O(H), where H is the height of the tree. This is due to the recursive call stack. In the worst case (a skewed tree), H can be N.

class Solution:
    def postorder(self, root: 'Node') -> List[int]:
        ans = []
        def dfs(root):
            if root is None:
                return
            for child in root.children:
                dfs(child)
            ans.append(root.val)
        dfs(root)
        return ans

Other languages (Java, C++, Go, TypeScript) follow a very similar recursive structure.

Solution 2: Iteration (using Stack)

This iterative approach uses a stack to simulate the recursive calls.

1. Initialization: It starts with a stack containing the root node.
2. Iteration: While the stack is not empty:
   • It pops the top node from the stack.
   • It appends the node's value to the ans list. Crucially, this happens after processing the children.
   • It pushes the node's children onto the stack (in reverse order to maintain the postorder sequence).
3. Reversal (Python): In Python, since we are appending to the beginning of ans, we need to reverse the list at the end to get the correct postorder sequence. Other languages might directly prepend to get the correct order.

Time Complexity: O(N), where N is the number of nodes in the tree. Each node is visited and processed once.

Space Complexity: O(N), where N is the number of nodes. In the worst-case scenario (a completely unbalanced tree), the stack could hold all nodes.

class Solution:
    def postorder(self, root: 'Node') -> List[int]:
        ans = []
        if root is None:
            return ans
        stk = [root]
        while stk:
            node = stk.pop()
            ans.append(node.val)
            for child in node.children:
                stk.append(child)
        return ans[::-1] # Reverse for Python

The iterative solutions in other languages (Java, C++, Go, TypeScript) are similar, but might handle the order of appending differently (e.g., using a LinkedList in Java to directly prepend, thereby avoiding the final reversal step). The core principle—using a stack to mimic recursion—remains consistent across all languages.