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 constructor(val, children = []) {
3 this.val = val;
4 this.children = children;
5 }
6}
7
8const preorder = function(root) {
9 const result = [];
10 const preorderHelper = (node) => {
11 if (!node) return;
12 result.push(node.val);
13 for (const child of node.children) {
14 preorderHelper(child);
15 }
16 };
17 preorderHelper(root);
18 return result;
19};The JavaScript implementation defines a Node class. The preorderHelper function recursively traverses nodes in preorder, recording their values in result and manages child traversal using the helper method.
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
The Python code introduces a list-based manual stack managing the work of the traversal, maintaining the order of the node children such that earlier nodes are faced first due to reversing incorporation into the stack.