# N-ary Tree Preorder Traversal

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 the below examples):

Example 1:

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

Example 2:

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

First of all, here is the definition of the tree `Node` which we would use in the following implementation.

```// Definition for a Node.
class Node {
public int val;
public List<Node> children;

public Node() {}

public Node(int _val,List<Node> _children) {
val = _val;
children = _children;
}
}
```

Let’s start from the root and then at each iteration pop the current node out of the stack and push its child nodes. In the implemented strategy we add nodes into output list by following the order `Top->Bottom` and `Left->Right`, that naturally reproduces preorder traversal.

```class Solution {
public List<Integer> preorder(Node root) {
List<Integer> result = new ArrayList<>();
if (root == null) return result;

Stack<Node> stack = new Stack<>();

while (!stack.isEmpty()) {
Node curr = stack.pop();
for (int i = curr.children.size() - 1; i >= 0; i--) {
stack.push(curr.children.get(i));
}
}
return result;
}
}
```

Complexity Analysis

• Time Complexity : we visit each node exactly once, and for each visit, the complexity of the operation (i.e. appending the child nodes) is proportional to the number of child nodes `n` (n-ary tree). Therefore the overall time complexity is `O(N)`, where `N` is the number of nodes, i.e. the size of tree.
• Space Complexity : Depending on the tree structure, we could keep up to the entire tree, therefore, the space complexity is `O(N)`. The output list does not comes under the space complexity considerations.

Following is a recursive solution:

```class Solution {
public List<Integer> preorder(Node root) {
List<Integer> result = new ArrayList<>();
if (root == null) return result;
traversePreOrder(root, result);
return result;
}

private void traversePreOrder(Node root, List<Integer> result) {
if (root == null) return;