N-ary Tree Preorder Traversal

Difficulty: Easy | Acceptance: 76.80% | Paid: No Topics: Stack, Tree, Depth-First Search

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 traversal. Each group of children is separated by the null value (See examples).

• Examples
• Constraints
• Recursive Depth-First Search
• Iterative Depth-First Search

Examples

Example 1:

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

Example 2:

Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
Output: [1,2,3,6,7,11,14,4,8,12,5,9,13,10]

Constraints

The number of nodes in the tree is in the range [0, 10⁴].
0 <= Node.val <= 10⁴.
The height of the n-ary tree is less than or equal to 1000.

Recursive Depth-First Search

Intuition Preorder traversal visits the root node first, followed by its children from left to right. This naturally lends itself to a recursive approach where we process the current node and then recursively process each child.

Steps

• Check if the root is null. If so, return an empty list.
• Initialize a result list.
• Create a recursive helper function that takes a node as input.
• Inside the helper, add the node’s value to the result list.
• Iterate through the node’s children and call the helper function for each child.
• Call the helper with the root and return the result list.

class Solution:
    def preorder(self, root: 'Node') -> List[int]:
        res = []
        
        def dfs(node):
            if not node:
                return
            res.append(node.val)
            for child in node.children:
                dfs(child)
                
        dfs(root)
        return res

Complexity

• Time: O(N), where N is the number of nodes in the tree. We visit each node exactly once.
• Space: O(N), in the worst case of a skewed tree (essentially a linked list), the recursion stack can grow as deep as the number of nodes.
• Notes: Simple and readable, but may cause a stack overflow for extremely deep trees due to recursion limits.

Iterative Depth-First Search

Intuition We can simulate the recursive approach using an explicit stack. The key is to push children onto the stack in reverse order so that the leftmost child is processed first (LIFO property of stacks).

Steps

• Check if the root is null. If so, return an empty list.
• Initialize a stack with the root node and an empty result list.
• While the stack is not empty:
  • Pop the top node from the stack.
  • Add the node’s value to the result list.
  • Iterate through the node’s children in reverse order and push them onto the stack.
• Return the result list.

class Solution:
    def preorder(self, root: 'Node') -> List[int]:
        if not root:
            return []
        
        stack = [root]
        res = []
        
        while stack:
            node = stack.pop()
            res.append(node.val)
            # Add children in reverse order to process left-to-right
            for child in reversed(node.children):
                stack.append(child)
                
        return res

Complexity

• Time: O(N), where N is the number of nodes. Each node is pushed and popped from the stack exactly once.
• Space: O(N), to store the stack and the result list. In the worst case, the stack holds all nodes (e.g., root has many children).
• Notes: Avoids recursion depth limits and is generally preferred in production environments for traversals that might be deep.