N-ary Tree Preorder and Postorder Traversal — LC 589 and LC 590

Problem Statement#

LeetCode 589 — N-ary Tree Preorder Traversal | Difficulty: Easy LeetCode 590 — N-ary Tree Postorder Traversal | Difficulty: Easy

Given the root of an n-ary tree, return its preorder (root, then all children left to right) and postorder (all children left to right, then root) traversals.

Constraints:

• The number of nodes is in the range [0, 10^4]
• 0 <= Node.val <= 10^4
• The height of the n-ary tree is at most 1000

Input:  root = [1,null,3,2,4,null,5,6]
Preorder Output:  [1,3,5,6,2,4]
Postorder Output: [5,6,3,2,4,1]

Input:  root = []
Preorder Output:  []
Postorder Output: []

Why This Problem Matters#

N-ary tree traversals generalize binary tree DFS to trees where each node can have any number of children. Amazon and Google include these in interview pools as warm-up problems and as prerequisites for harder tree questions like LC 428 (Serialize and Deserialize N-ary Tree), LC 1443 (Minimum Time to Collect Apples), and LC 863 (All Nodes Distance K).

The iterative implementations using a stack are also common interview questions — particularly the iterative postorder, which requires reversing the order of child processing relative to preorder.

The Core Insight#

Preorder visits root before all children: emit root.val, then recursively visit each child.

Postorder visits all children before root: recursively visit each child, then emit root.val.

The only difference from binary tree traversal is iterating over node.children instead of handling node.left and node.right separately. The structure is identical.

Iterative preorder trick: push children onto a stack in reverse order so left-most child is processed first (stacks pop from the top, so push right-to-left).

Iterative postorder trick: collect values like a reversed preorder (root, right-to-left children), then reverse the final list.

Visual Dry Run#

Tree: root = 1, children of 1: [3, 2, 4], children of 3: [5, 6]

Preorder DFS:

• Visit 1 → emit 1
• Visit 3 → emit 3
• Visit 5 → emit 5 (leaf)
• Visit 6 → emit 6 (leaf)
• Visit 2 → emit 2 (leaf)
• Visit 4 → emit 4 (leaf)

Preorder: [1, 3, 5, 6, 2, 4]

Postorder DFS:

• Visit 5 → emit 5
• Visit 6 → emit 6
• Done with 3's children → emit 3
• Done with 2 → emit 2
• Done with 4 → emit 4
• Done with 1's children → emit 1

Postorder: [5, 6, 3, 2, 4, 1]

Solution (Optimal)#

# Preorder: LC 589
class Solution:
    def preorder(self, root):
        if not root:
            return []
        result = [root.val]
        for child in root.children:
            result.extend(self.preorder(child))
        return result
 
# Postorder: LC 590
class Solution:
    def postorder(self, root):
        if not root:
            return []
        result = []
        for child in root.children:
            result.extend(self.postorder(child))
        result.append(root.val)
        return result
 
# Iterative preorder
def preorderIterative(root):
    if not root:
        return []
    result = []
    stack = [root]
    while stack:
        node = stack.pop()
        result.append(node.val)
        # Push children in reverse so leftmost is processed first
        for child in reversed(node.children):
            stack.append(child)
    return result

// Preorder: LC 589
var preorder = function(root) {
    if (!root) return [];
    return [root.val, ...root.children.flatMap(preorder)];
};
 
// Postorder: LC 590
var postorder = function(root) {
    if (!root) return [];
    return [...root.children.flatMap(postorder), root.val];
};
 
// Iterative preorder
function preorderIterative(root) {
    if (!root) return [];
    const result = [];
    const stack = [root];
    while (stack.length) {
        const node = stack.pop();
        result.push(node.val);
        // Push children in reverse order
        for (let i = node.children.length - 1; i >= 0; i--) {
            stack.push(node.children[i]);
        }
    }
    return result;
}

Time: O(n) — each node visited exactly once Space: O(n) — result array stores all n values; call stack is O(h)

Common Mistakes#

• Forgetting to iterate over all children instead of just left/right — n-ary trees have variable child counts
• Returning early without processing all children — each child must be visited in order
• Iterative preorder pushing children left-to-right (without reversing) — this processes rightmost child first
• In Python, accidentally mutating a shared list across recursive calls instead of using extend

Interview Tips#

• State that n-ary traversal is a direct generalization of binary tree traversal — same structure, loop over children instead of left/right
• The iterative versions are worth knowing: iterative preorder uses a stack with reversed children; iterative postorder reverses the result of a modified preorder
• Show both recursive and iterative implementations if the interviewer asks for "no recursion"

Follow-up Questions#

• How would you do level-order (BFS) traversal of an n-ary tree? Use a queue — same as binary tree BFS, but enqueue all children of each node instead of just left/right.
• How does serialization change for n-ary trees? Include a child count at each node (or use a sentinel "end of children" marker) in the preorder string.
• What is the iterative postorder without reversing? Use two stacks — the second stack collects nodes in reverse postorder, then reverse it at the end.
• How does this extend to other tree DP problems on n-ary trees? Same post-order structure — process all children before the current node, then combine results.

Key Takeaways#

• N-ary preorder: emit root, then recursively visit all children left to right
• N-ary postorder: recursively visit all children left to right, then emit root
• The only change from binary tree DFS is for child in node.children instead of handling left/right separately
• Iterative preorder: use a stack, push children in reverse order so leftmost is processed first
• Iterative postorder: collect like a modified preorder (push children left-to-right), then reverse the result
• Time O(n), space O(n) — same as binary tree traversal
• Mastering n-ary traversal is essential for harder problems like LC 428, LC 1443, and any problem involving file system or DOM tree traversal