> For the complete documentation index, see [llms.txt](https://ucan.gitbook.io/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://ucan.gitbook.io/notes/tree/589.-n-ary-tree-preorder-traversal.md).

# 589. N-ary Tree Preorder Traversal

[Given an n-ary tree, return the preorder traversal of its nodes' values.](https://leetcode.com/problems/n-ary-tree-preorder-traversal/)

DFS:

```java
class Solution {
    public List<Integer> preorder(Node root) {
        List<Integer> res = new ArrayList<>();
        if (root!=null) dfs(root,res);
        return res;
    }
    private void dfs(Node node, List<Integer> list){
        list.add(node.val);
        for(Node child : node.children){
            dfs(child, list);
        }
    }   
}
```

Iteration

```java
class Solution {
    public List<Integer> preorder(Node root) {
        // use stack to mock dfs
        Stack<Node> stack = new Stack<>();
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;
        stack.add(root);
        while (!stack.isEmpty()){
            Node node = stack.pop();
            res.add(node.val);
            // list support iterate from end to head
            for (int i=node.children.size()-1; i>=0; i--){
                stack.add(node.children.get(i));
            }
        }
        return res;
    }
}
```