algoadvance

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).

Example:

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

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,4,8,9,10,5,11,12,13,14]

Clarifying Questions:

  1. What should we return if the input tree is empty?
    • Return an empty list if the root is None.
  2. Are there any constraints on the values of the nodes or the depth of the tree?
    • This is not specified, we can assume there’s no constraint on node values or tree depth.

Strategy:

  1. Preorder Traversal:
    • Preorder traversal visits nodes in the following order: Root, Children from left to right.
  2. Recursive Approach:
    • Define a helper function that recursively performs preorder traversal.
    • Traverse the root node first and append it to the result list.
    • Recursively visit and traverse each child node in sequence.
  3. Iterative Approach:
    • Also, consider an iterative approach using a stack if recursion is limited by depth issues.

Code:

Recursive Preorder Traversal:

# 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[int]:
        def traverse(node):
            if node is None:
                return
            result.append(node.val)
            for child in node.children:
                traverse(child)
        
        result = []
        traverse(root)
        return result

Iterative Preorder Traversal:

class Solution:
    def preorder(self, root: 'Node') -> List[int]:
        if root is None:
            return []
        
        stack, result = [root], []
        while stack:
            node = stack.pop()
            result.append(node.val)
            stack.extend(reversed(node.children))
        return result

Time Complexity:

Both techniques ensure that all nodes are visited and processed in preorder fashion. The space complexity is O(n) in the worst case due to the recursion stack or the explicit stack used for traversal.

Try our interview co-pilot at AlgoAdvance.com