N-ary Tree Postorder Traversal

How it works

To convert the recursive solution to an iterative one, we use a stack. The key challenge is ensuring we process a node only after all its children have been processed. We achieve this by pushing each node onto the stack twice: once to signal that its children should be explored, and once to signal that it should be added to the result. A visited flag distinguishes between these two cases. When we pop a node that has been visited, we add it to the result. When we pop an unvisited node, we mark it as visited, push it back, then push all its children in reverse order.

Steps

1. If the root is null, return an empty list.
2. Initialize a stack with the pair (root, false), where false indicates the node has not been visited.
3. While the stack is not empty:
   • Pop a pair (node, visited).
   • If visited is true, add node.val to the result.
   • Otherwise, push (node, true) back onto the stack, then push all children in reverse order as (child, false).
4. Return the result list.

Complexity

• Time complexity: O(n)
• Space complexity: O(n)

Things to watch for

Appending Node Value Before Processing Children

In postorder traversal, the node's value must be added to the result after all its children have been processed. A common mistake is appending the node's value before or during the iteration over children. This produces preorder output instead of postorder. Always ensure the res.append(node.val) statement comes after the loop that recursively processes all children.

Forgetting to Reverse Children Order in Iterative Approach

When using an explicit stack for iterative postorder traversal, children must be pushed in reverse order so that the leftmost child is processed first. If you push children in their natural order, the rightmost child will be popped and processed first, resulting in incorrect traversal order. Always iterate through children in reverse when adding them to the stack.

from typing import List

"""
# Definition for a Node.
class Node:
    def __init__(self, val: Optional[int] = None, children: Optional[List['Node']] = None):
        self.val = val
        self.children = children
"""

class Solution:
    def postorder(self, root: 'Node') -> List[int]:
        res = []
        if not root:
            return res

        stack = [(root, False)]
        while stack:
            node, visited = stack.pop()
            if visited:
                res.append(node.val)
            else:
                stack.append((node, True))
                for child in reversed(node.children):
                    stack.append((child, False))
        return res

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    vector<int> postorder(Node* root) {
        vector<int> res;
        if (!root) return res;

        stack<pair<Node*, bool>> st;
        st.push({root, false});

        while (!st.empty()) {
            auto [node, visited] = st.top();
            st.pop();

            if (visited) {
                res.push_back(node->val);
            } else {
                st.push({node, true});
                for (int i = (int)node->children.size() - 1; i >= 0; i--) {
                    st.push({node->children[i], false});
                }
            }
        }

        return res;
    }
};