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:

1. The current node.
2. 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

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:

        1
      / | \
     3  2  4
    / \
   5   6

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:

1. Add the node’s value to the answer.
2. 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

1. Create an empty result list.
2. Define a DFS function.
3. If the current node is None, stop.
4. Append the current node’s value.
5. For each child in node.children, recursively call DFS.
6. 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

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: