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.
1
The C code defines a node structured to represent each tree node with value and children. Using a helper function, preorderHelper, it ensures the tree is traversed in preorder by accessing each node's value before recursively calling the helper on each child.
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.
1import java.util.ArrayList;
2import java.util.Collections;
3import java.util.List;
4import java.util.Stack;
5
6class Node {
7 public int val;
8 public List<Node> children;
9
10 public Node() {}
11
12 public Node(int _val) {
13 val = _val;
14 }
15
16 public Node(int _val, List<Node> _children) {
17 val = _val;
18 children = _children;
19 }
20};
21
22class Solution {
23 public List<Integer> preorder(Node root) {
24 List<Integer> result = new ArrayList<>();
25 if (root == null) return result;
26
27 Stack<Node> stack = new Stack<>();
28 stack.push(root);
29
30 while (!stack.isEmpty()) {
31 Node node = stack.pop();
32 result.add(node.val);
33
34 List<Node> children = new ArrayList<>(node.children);
35 Collections.reverse(children);
36 for (Node child : children) {
37 stack.push(child);
38 }
39 }
40 return result;
41 }
42}Java's solution employs a stack for principal control of order. The Stack collects children in reverse order, establishing valid sequential preorder outcomes in the iterative node evaluation.