# 0589. Preorder Traversal

{% tabs %}
{% tab title="❓ Problem Statement" %}

> Source: [LeetCode - N-ary Tree Preorder Traversal](https://leetcode.com/problems/n-ary-tree-preorder-traversal/)\
> GitHub: [Solution / Performance](https://github.com/yylou/leetcode/tree/main/0589-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 examples)

**Follow up:** Recursive solution is trivial, could you do it iteratively?
{% endtab %}

{% tab title="✍🏻 Constraints & Example" %}
**Constraints:**

* The number of nodes in the tree is in the range `[0, 10^4]`.
* `0 <= Node.val <= 10^4`
* The height of the n-ary tree is less than or equal to `1000`.
  {% endtab %}
  {% endtabs %}

{% tabs %}
{% tab title="💡 Ideas" %}
{% hint style="info" %}
For **recursive solution**, visiting the children (list of nodes) in the **right order**.

For **iterative solution**, visiting the children (list of nodes) **reversely**.
{% endhint %}

Excepting the above hints, we **append each node's value first** before visiting the child nodes.
{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title=" 🤖 Python3" %}

```python
class Solution:
    def preorder(self, root: 'Node') -> List[int]:
        # (base case)
        if not root: return []
        if not root.children: return [root.val]
        
        # ==================================================
        #  N-ary Tree + Pre-order Traversal   (Iterative)  =
        # ==================================================
        # time  : O(n)
        # space : O(n)
        
        ans = []
        stack = [root]
        
        while stack:
            node = stack.pop()
            ans.append(node.val)
            
            if node.children:
                for i in range(len(node.children)-1, -1, -1):
                    stack.append(node.children[i])
                
        return ans
        
        '''
        # ==================================================
        #  N-ary Tree + Pre-order Traversal   (Recursive)  =
        # ==================================================
        # time  : O(n)
        # space : O(n)
        
        ans = []
        
        def recursive(node: 'Node') -> None:
            ans.append(node.val)
            
            if node.children:
                for element in node.children:
                    recursive(element)
        
        recursive(root)
        return ans
        '''
```

{% endtab %}

{% tab title=" 🤖 Java" %}

```java
class Solution {
    /**
     * @time  : O(n)
     * @space : O(n)
     */
    
    LinkedList<Integer> answer;
    
    public List<Integer> preorder(Node root) {
        answer = new LinkedList<Integer>();
        
        /* base case */
        if(root == null) return answer;
        
        answer.add(root.val);
        
        if(root.children == null) return answer;
        
        for(Node node: root.children) {
            recursive(node);
        }
        
        return answer;
    }
    
    public void recursive(Node root) {
        answer.add(root.val);
        
        if(root.children != null ) {
            for(Node node: root.children) {
                recursive(node);
            }
        }
    }
}
```

{% endtab %}
{% endtabs %}


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://yyloumike.gitbook.io/leetcode/tree/n-ary-tree-traversal-3-qs/0589.-n-ary-tree-preorder-traversal.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.