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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

N-ary Tree Preorder Traversal

Difficulty: Easy

Problem Description

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

Key Insights

  • Preorder traversal visits the root node first, followed by the children nodes from left to right.
  • An n-ary tree can have an arbitrary number of children for each node.
  • The problem can be solved using both recursive and iterative approaches.
  • Stack data structure is useful for implementing the iterative traversal.

Space and Time Complexity

Time Complexity: O(N), where N is the number of nodes in the tree, as we visit each node once. Space Complexity: O(N), for the stack space used in the iterative approach or O(H) for the recursive approach, where H is the height of the tree.

Solution

To solve the problem of N-ary tree preorder traversal, we can use either recursion or iteration. The iterative approach will utilize a stack to keep track of the nodes to be visited.

  1. Start by initializing a stack with the root node.
  2. While the stack is not empty, pop the top node, visit it (add its value to the results list), and then push its children onto the stack in reverse order (to maintain the correct order for traversal).
  3. Continue this process until all nodes have been visited.

This approach ensures that we traverse each node precisely in the order required for preorder traversal.

Code Solutions

def preorder(root):
    if not root:
        return []
    
    result = []
    stack = [root]
    
    while stack:
        node = stack.pop()
        result.append(node.val)
        # Add children in reverse order to maintain left-to-right traversal
        for child in reversed(node.children):
            stack.append(child)
    
    return result
← Back to All Questions