Skip to main content

589 - N-ary Tree Preorder Traversal

Difficulty: Easy | Pattern: Tree DFS | Company tags: Amazon, Google, Microsoft

Problem Statement​

Given the root of an n-ary tree, return the preorder traversal of its nodes' values.

Nary-Tree input serialization is represented in their level order, with each group of children separated by null.

Example:

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

Solution: Recursive — O(n), O(h)​

def preorder(root) -> list[int]:
    result = []
    def dfs(node):
        if not node:
            return
        result.append(node.val)  # pre: process before children
        for child in node.children:
            dfs(child)
    dfs(root)
    return result

Solution: Iterative (Stack) — O(n), O(n)​

Key insight: Push children in reverse order so leftmost is processed first.

def preorder(root) -> list[int]:
    if not root:
        return []
    result = []
    stack = [root]
    
    while stack:
        node = stack.pop()
        result.append(node.val)
        # Push children right-to-left so left child is popped first
        for child in reversed(node.children):
            stack.append(child)
    
    return result

Algorithm Flow​

Dry Run​

Tree: 1 → children [3,2,4]; 3 → children [5,6]

Iterative: stack=[1]

  • pop 1 → result=[1], push [4,2,3]
  • pop 3 → result=[1,3], push [6,5]
  • pop 5 → result=[1,3,5]
  • pop 6 → result=[1,3,5,6]
  • pop 2 → result=[1,3,5,6,2]
  • pop 4 → result=[1,3,5,6,2,4] ✓

Traversal Orders for N-ary Trees​

  • Preorder: root → all children (LC 589)
  • Postorder: all children → root (LC 590)
  • Level order: BFS (LC 429)

Complexity​

  • Time: O(n)
  • Space: O(h) recursive, O(n) iterative

Key Terms​

TermDefinition
N-ary treeA tree where each node can have any number of children, stored as a list (node.children).
Preorder traversalVisit order of root → children (left to right); the node is processed before its subtrees.
DFS (Depth-First Search)Traversal strategy that fully explores one branch before backtracking to the next.
Explicit stackA manually managed LIFO structure used to simulate recursion iteratively.
Call stackThe implicit stack the runtime uses to track recursive dfs() calls and their return addresses.

FAQ​

Q1: Why push children in reverse order in the iterative solution? A: The stack is LIFO, so pushing right-to-left means the leftmost child is pushed last and popped first, preserving left-to-right preorder output.

Q2: How does this differ from binary tree preorder traversal? A: The logic is identical, but instead of left/right pointers you iterate over node.children, a variable-length list, so the loop replaces the two fixed recursive calls.

Q3: What's the space complexity difference between the recursive and iterative versions? A: Recursive uses O(h) space for the call stack (h = tree height); iterative uses O(n) worst case because it can hold up to all nodes' siblings-in-waiting on the stack simultaneously.

Q4: Can this be solved with O(1) extra space? A: Not without modifying the tree structure (unlike Morris traversal for binary trees, which relies on two child pointers); n-ary trees have no unused pointer to exploit, so O(h) or O(n) auxiliary space is standard.

Q5: What follow-up questions do interviewers typically ask after this? A: Convert to postorder, do it iteratively without extra space, handle very deep/wide trees, or serialize/deserialize the n-ary tree.

Quick Revision​

  • Problem: return preorder (root-then-children) traversal of an n-ary tree.
  • Recursive: process node.val, then recurse over each child left to right.
  • Iterative: use an explicit stack; pop a node, record its value, push children in reverse so leftmost pops first.
  • Time complexity: O(n) — every node visited once.
  • Space complexity: O(h) recursive, O(n) iterative (worst case for wide/shallow trees).
  • Core invariant: node value is always appended before its children's values.
  • Common pitfall: forgetting to reverse children order when pushing to a stack.
  • Edge cases: empty tree (root = None), single node, node with no children.
  • 429 - N-aryTreeLevelOrderTraversal — same n-ary tree structure, BFS instead of DFS.
  • 590 - N-ary Tree Postorder Traversal — same tree, children processed before the node (no file in this set yet).
  • 144 - Binary Tree Preorder Traversal — same preorder pattern restricted to two children (no file in this set yet).