LeetCode 589: N-ary Tree Preorder Traversal

Problem Restatement

We are given the root of an N-ary tree.

An N-ary tree is a tree where each node can have any number of children.

We need to return the preorder traversal of the tree's node values. In preorder traversal, we visit:

The current node.
Its children from left to right.

The number of nodes is in the range [0, 10^4], node values are between 0 and 10^4, and the tree height is at most 1000. The follow-up asks for an iterative solution.

Input and Output

Item	Meaning
`root`	Root node of an N-ary tree
Output	List of node values in preorder
Empty tree	Return `[]`

The node structure is usually given as:

class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children

Example function shape:

def preorder(root: "Node") -> list[int]:
    ...

Examples

Example 1:

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

This represents:

Output:

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

We visit 1 first, then the subtree rooted at 3, then 2, then 4.

Example 2:

root = []

Output:

[]

An empty tree has no nodes to visit.

First Thought: Recursive DFS

Preorder traversal is naturally recursive.

For each node:

Add the node's value to the answer.
Recursively visit each child from left to right.

This matches the definition of preorder exactly.

Key Insight

A tree traversal is a depth-first search.

For preorder, the node is processed before its children.

So the recursive rule is:

visit node
then visit each child in order

For an N-ary tree, the only difference from a binary tree is that instead of left and right, each node has a list of children.

Algorithm

Create an empty result list.
Define a DFS function.
If the current node is None, stop.
Append the current node's value.
For each child in node.children, recursively call DFS.
Return the result list.

Correctness

The algorithm appends a node's value before visiting any of its children. This matches the first rule of preorder traversal.

Then it visits the children in the same left-to-right order as they appear in node.children. For each child, the same rule is applied recursively, so the entire child subtree is traversed in preorder before moving to the next child.

The base case handles an empty node by adding nothing, which is correct for an empty subtree.

Therefore, the result contains exactly the preorder traversal of the N-ary tree.

Complexity

Let:

n = number of nodes in the tree
h = height of the tree

Metric	Value	Why
Time	`O(n)`	Each node is visited once
Space	`O(h)`	The recursion stack can contain one path from root to leaf

The output list also uses O(n) space.

Implementation

"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""

class Solution:
    def preorder(self, root: "Node") -> list[int]:
        result = []

        def dfs(node: "Node") -> None:
            if node is None:
                return

            result.append(node.val)

            for child in node.children:
                dfs(child)

        dfs(root)

        return result

Code Explanation

The result list stores the traversal:

result = []

The helper function visits one subtree:

def dfs(node):

The empty tree case is:

if node is None:
    return

For preorder, we append the current value before visiting children:

result.append(node.val)

Then we recursively traverse each child:

for child in node.children:
    dfs(child)

Finally, the traversal starts at the root:

dfs(root)

Iterative Implementation

The follow-up asks for an iterative solution.

Use a stack.

The main detail is child order. Since a stack is last-in, first-out, we push children in reverse order. That makes the leftmost child processed first.

class Solution:
    def preorder(self, root: "Node") -> list[int]:
        if root is None:
            return []

        result = []
        stack = [root]

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

            for child in reversed(node.children):
                stack.append(child)

        return result

For example, if node 1 has children:

[3, 2, 4]

we push them as:

4, 2, 3

Then 3 is popped first, preserving preorder.

Testing

class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children or []

def run_tests():
    s = Solution()

    root = Node(1, [
        Node(3, [Node(5), Node(6)]),
        Node(2),
        Node(4),
    ])
    assert s.preorder(root) == [1, 3, 5, 6, 2, 4]

    assert s.preorder(None) == []

    single = Node(1)
    assert s.preorder(single) == [1]

    chain = Node(1, [Node(2, [Node(3)])])
    assert s.preorder(chain) == [1, 2, 3]

    wide = Node(1, [Node(2), Node(3), Node(4)])
    assert s.preorder(wide) == [1, 2, 3, 4]

    print("all tests passed")

run_tests()

Test meaning:

Test	Why
Sample tree	Checks standard preorder behavior
Empty tree	Returns an empty list
Single node	Returns only the root
Deep chain	Checks recursion down one path
Wide tree	Checks children are visited left to right