We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

N-ary Tree Preorder Traversal

Number: 775

Difficulty: Easy

Paid? No

Companies: Google

Problem Description

Given the root of an N-ary tree, return the preorder traversal of its nodes' values. The N-ary tree is serialized in level order where each group of children is divided by a null value. The challenge is to perform a preorder traversal (root, then children) iteratively without using recursion.

Key Insights

  • Preorder traversal visits the root node first and then recursively visits each child from left to right.
  • An iterative solution can mimic recursion by using a stack.
  • When using a stack, push the children in reverse order so that the leftmost child is processed first.
  • The iterative approach avoids potential stack overflow issues due to recursion with deeply nested trees.

Space and Time Complexity

Time Complexity: O(N), where N is the number of nodes, because each node is visited exactly once.
Space Complexity: O(N) in the worst case (e.g., when the tree is skewed), due to the stack used for traversal.

Solution

The solution uses an iterative approach with a stack data structure to perform a preorder traversal. We start by pushing the root node onto the stack. In each iteration, pop the node from the stack, record its value, and push its children onto the stack in reverse order. Pushing in reverse ensures that the leftmost child is processed next. This simulates the call stack of a recursive solution while using explicit stack management.

Code Solutions

# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children if children is not None else []

class Solution:
    def preorder(self, root: 'Node') -> list:
        # List to store the traversal order
        result = []
        # Edge case: if the tree is empty, return empty list
        if root is None:
            return result
        
        # Use stack to mimic recursion, initialize with the root node
        stack = [root]
        
        while stack:
            # Pop the current node from stack
            current = stack.pop()
            # Record the node value
            result.append(current.val)
            # Push children in reverse order to ensure left-to-right traversal
            for child in reversed(current.children):
                stack.append(child)
        
        return result
← Back to All Questions