N-ary Tree Preorder Traversal: DFS Without Recursion

Given an n-ary tree, return the preorder traversal of its nodes' values. Preorder means you visit the root first, then recursively visit each child from left to right. Each node can have any number of children. This is LeetCode 589: N-ary Tree Preorder Traversal.

For example, given the tree below with root = 1, children [3, 2, 4], and node 3 having children [5, 6], the preorder output is [1, 3, 5, 6, 2, 4].

Why this problem matters

If you have solved Binary Tree Preorder Traversal (LeetCode 144), you already know the core pattern: use a stack, pop a node, record its value, push its children. This problem asks you to generalize that pattern from binary trees to n-ary trees.

The difference is small but worth understanding. In a binary tree, you push right then left so that left gets popped first. In an n-ary tree, you push the children in reverse order so the leftmost child ends up on top of the stack. That single change is the only thing separating the two problems.

Preorder traversal shows up whenever you need to process a parent before its descendants. Think of serializing a file system tree, copying a nested data structure, or generating a table of contents from a heading hierarchy. Once you can do iterative preorder on an n-ary tree, you can handle any tree-shaped data.

The approach

The algorithm uses an explicit stack to simulate the recursive preorder traversal:

1. Push the root onto the stack.
2. While the stack is not empty, pop the top node, append its value to the result, and push its children in reverse order.
3. Reversing the children ensures the leftmost child is processed next (since it lands on top of the stack).

def preorder(root):
    if not root:
        return []

    result = []
    stack = [root]

    while stack:
        node = stack.pop()
        result.append(node.val)
        stack.extend(reversed(node.children))

    return result

Here is what each part does:

• stack = [root] seeds the stack with the root node. It will be the first node popped and recorded.
• node = stack.pop() grabs the most recently added node, which is always the next node in preorder.
• result.append(node.val) records the node's value before exploring its children. That is the "pre" in preorder.
• stack.extend(reversed(node.children)) is the key line. By reversing the children, the leftmost child ends up on top of the stack, so it gets popped next. This guarantees left-to-right processing.

Step-by-step walkthrough

Let's trace the iterative DFS through the n-ary tree with root 1, children [3, 2, 4], and node 3 having children [5, 6]. Watch how the stack drives the traversal deep into the left subtree before backtracking.

Notice the pattern. Each pop records a value and pushes reversed children. The stack naturally handles backtracking: once a subtree is fully explored, the next sibling is already sitting on the stack waiting to be processed.

Complexity analysis

For a deep, narrow tree, the stack holds at most the depth of the tree. But we express the worst case as O(n) because a root with n-1 children would put all of them on the stack at once.

Edge cases to watch for

• Empty tree (root is None): return an empty list []. The guard clause at the top handles this.
• Single node (no children): return [root.val]. The stack pops the root, finds no children, and the loop ends.
• Node with many children: reversed(node.children) works for any list length, so a node with 100 children is handled the same way as one with 2.
• Deep, unbalanced tree: produces output like [a, b, c, ...] going straight down. The stack depth equals the tree depth, which is fine.
• All children are leaves: the root is popped first, then all children are pushed and popped one by one. The output is root followed by all children left to right.

The building blocks

This problem is built on one core pattern: iterative DFS with a stack. The only twist compared to binary tree preorder is using reversed(node.children) instead of pushing right then left.

Once you internalize the stack-based DFS template, you can apply it across a family of related problems:

• Binary Tree Preorder Traversal (LeetCode 144): the binary tree version of this same pattern, where you push right then left.
• N-ary Tree Level Order Traversal (LeetCode 429): same tree structure, but uses BFS with a queue instead of DFS with a stack.

The n-ary version reinforces that DFS does not depend on a fixed branching factor. The template works on any tree as long as you can enumerate a node's children.

From understanding to recall

You just traced through an iterative preorder traversal and watched the stack manage backtracking automatically. The logic is clear right now. But when you see this problem in an interview next month, will you remember to reverse the children before pushing? Will you confidently reach for a stack instead of writing a recursive solution?

Understanding a pattern and reproducing it under pressure are different skills. Spaced repetition bridges that gap. You practice the iterative DFS template from memory at increasing intervals - first after a day, then three days, then a week. Each repetition reinforces the stack management, the reversal trick, and the "process before pushing children" flow until it becomes automatic.

Related posts

• N-ary Tree Level Order Traversal - Same n-ary tree structure processed with BFS instead of DFS
• Binary Tree Preorder Traversal - The binary tree version of iterative preorder, and the foundation this problem builds on
• Binary Tree Inorder Traversal - Another traversal order using a stack, with a different push/pop rhythm