N-ary Tree Preorder Traversal
Traverse a tree whose nodes have any number of children, recursively and iteratively
Problem Statement
Given the root of an n-ary tree — a tree where each node can have any number of children — return the preorder traversal of its node values.
Preorder means: visit the node first, then traverse each child in order.
Input: 1
/ | \
3 2 4
/ \
5 6
Output: [1, 3, 5, 6, 2, 4]
Order: root → subtree(3) fully → 2 → 4Intuition
Preorder has a one-line recursive definition:
The key insight
Visit the node, then recursively traverse each child, left to right.
For a binary tree that is node, left, right. For an n-ary tree it is node, child₁, child₂, …, childₖ. The only change is that the fixed pair of children becomes a loop over a list.
The word "pre" refers to when the node itself is recorded: before its children. The three classic orders differ only in where that one line sits:
| Order | Node recorded | Result for the example |
|---|---|---|
| Preorder | before the children | 1, 3, 5, 6, 2, 4 |
| Postorder | after the children | 5, 6, 3, 2, 4, 1 |
| Inorder | between children (binary trees only) | not defined for n-ary |
Real-world analogy
Reading a table of contents. You read a chapter title, then everything inside that chapter (including its subsections) before moving to the next chapter. Title first, contents after — that is preorder.
Watch it run
[1]Solution
Recursive
The definition translated directly into code.
from typing import Optional
class Node:
def __init__(self, val: int = 0, children: Optional[list["Node"]] = None):
self.val = val
self.children = children if children is not None else []
def preorder(root: Optional[Node]) -> list[int]:
"""Node values in preorder: node first, then each child in order."""
result: list[int] = []
def visit(node: Optional[Node]) -> None:
if node is None:
return
result.append(node.val) # record BEFORE descending
for child in node.children:
visit(child)
visit(root)
return resultIterative, with an explicit stack
Recursion uses the call stack; the iterative version manages that stack itself. This matters for very deep trees, where recursion would overflow.
def preorder_iterative(root: Optional[Node]) -> list[int]:
if root is None:
return []
result: list[int] = []
stack = [root]
while stack:
node = stack.pop()
result.append(node.val)
# Push children in REVERSE so the first child is popped first.
for child in reversed(node.children):
stack.append(child)
return resultWhy the children go on in reverse
A stack is last-in-first-out. Pushing children [3, 2, 4] in order makes 4 the top, so it would be visited first — the wrong order.
Pushing them reversed as 4, 2, 3 puts 3 on top, so it comes out first. Forgetting this reversal is the standard bug in iterative preorder.
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(h)
- Time — every node is visited exactly once, and every child link is followed once.
- Space —
O(h)wherehis the height, for either the call stack or the explicit stack. A balanced tree givesO(log n); a degenerate chain givesO(n).
Recursive or iterative?
The recursive version is shorter and reads like the definition — prefer it unless the tree can be deep. Python's default recursion limit is 1000 frames, so a chain of 10,000 nodes raises RecursionError, and JavaScript engines throw RangeError at a similar depth. That is when the explicit stack earns its extra lines.
Edge Cases
Related Problems
- Binary Tree Level Order Traversal — BFS, the breadth-first counterpart
- Valid Parentheses — the stack that DFS relies on
- Find the Town Judge — reasoning about node relationships without traversal