Sponsored
Sponsored
This approach leverages the simplicity of recursion to perform a preorder traversal on an n-ary tree. We start at the root node, then recursively process each child's subtree.
Time Complexity: O(n), where n is the number of nodes in the tree, since we visit each node once.
Space Complexity: O(n) for the recursion stack used in the helper function.
1class Node:
2 def __init__(self, val=None, children=None):
3 self.val = val
4 self.children = children if children is not None else []
5
6class Solution:
7 def preorder(self, root: 'Node') -> List[int]:
8 def preorder_helper(node, result):
9 if not node:
10 return
11 result.append(node.val)
12 for child in node.children:
13 preorder_helper(child, result)
14
15 result = []
16 preorder_helper(root, result)
17 return resultThe Python solution uses a nested helper function named preorder_helper that appends node values to a list, result, as it recursively explores each subtree's preorder traversal starting from the root.
This approach uses an explicit stack to simulate the call stack of recursion. We manually manage traversals seen in recursion, starting from the root node, iteratively processing each node, then adding each child to a stack for future visits.
Time Complexity: O(n). Space Complexity: O(n), as most nodes can be stored in the stack in the worst case.
1
JavaScript’s solution constructs a stack array replicating recursion with iterative needs. With each node processed, it takes its children in reverse order for correct simulated preorder traversal assurance.