# N-ary Tree Preorder Traversal

Easy

Given an n-ary tree, return thepreordertraversal of its nodes' values.

For example, given a`3-ary`tree:

Return its preorder traversal as:`[1,3,5,6,2,4]`.

Note:

Recursive solution is trivial, could you do it iteratively?

## Solution

``// Definition for a Node.``
``````/*
// 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;
}
};
*/``````

### DFS - Recursive

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

return res;
}

private void preorderHelper(Node root, List<Integer> res) {
if (root == null) {
return;
}

for (Node node: root.children) {
preorderHelper(node, res);
}
}
}``````

### DFS - Iterative

``````/*
// 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;
}
};
*/
class Solution {
public List<Integer> preorder(Node root) {

List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
Deque<Node> stack = new ArrayDeque<>();

stack.push(root);

while (!stack.isEmpty()) {
Node node = stack.pop();
if (node.children != null) {
Collections.reverse(node.children);
for (Node c: node.children) {
stack.push(c);
}
}
}
return res;
}
}``````

## Reference

https://leetcode.com/problems/n-ary-tree-preorder-traversal/solution/

Last updated