# N-ary Tree Preorder Traversal
**Difficulty:** EASY
[External](https://leetcode.com/problems/n-ary-tree-preorder-traversal)
Canonical: https://scaleengineer.com/dsa/problems/n-ary-tree-preorder-traversal
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Stack, Tree
---
## Problem
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)

**Example 1:**

![](https://assets.glich.co/dsa/n-ary-tree-preorder-traversal/image0.png)

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

**Example 2:**

![](https://assets.glich.co/dsa/n-ary-tree-preorder-traversal/image1.png)

**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]

**Constraints:**

* The number of nodes in the tree is in the range `[0, 104]`.
* `0 <= Node.val <= 104`
* The height of the n-ary tree is less than or equal to `1000`.

**Follow up:** Recursive solution is trivial, could you do it iteratively?

# Approaches
## Recursive Approach
The most intuitive way to perform a preorder traversal is using recursion. The definition of preorder traversal is to visit the root node first, and then traverse the subtrees of its children from left to right. This structure lends itself perfectly to a recursive function.
**Time:** O(N), where N is the total number of nodes in the tree. This is because we visit each node exactly once. · **Space:** O(H), where H is the height of the tree. In the worst-case scenario of a skewed tree (where each node has only one child), the height can be equal to the number of nodes N, leading to a space complexity of O(N). This space is used by the recursion call stack.
**Pros:** The code is simple, clean, and easy to understand as it directly mirrors the definition of preorder traversal.; It requires minimal boilerplate code.
**Cons:** For very deep trees, this approach can lead to a `StackOverflowError` because each recursive call adds a new frame to the system's call stack.
### Explanation
We can implement this with a helper function that performs the traversal. The main function initializes a list to store the results and calls the helper with the root. The helper function first checks if the node is null. If not, it adds the node's value to our result list. Then, it iterates through all the children of the current node, from the first to the last, and makes a recursive call for each child. This process naturally follows the 'root, then children' order of preorder traversal.

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

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

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

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

    private void traverse(Node node, List<Integer> result) {
        if (node == null) {
            return;
        }
        // Visit the root node first
        result.add(node.val);
        // Then, recursively traverse its children
        for (Node child : node.children) {
            traverse(child, result);
        }
    }
}
```
### Algorithm
*   Define a helper function, let's call it `traverse`, that takes a `Node` and a `List<Integer>` as arguments.
*   The main `preorder` function will initialize an empty list and call this helper function with the `root` node.
*   Inside the `traverse` function:
    1.  Check for the base case: if the current node is `null`, simply return.
    2.  Add the value of the current node to the list. This is the "visit" step in preorder (Root -> Left -> Right).
    3.  Iterate through the list of children of the current node.
    4.  For each child, make a recursive call to the `traverse` function, passing the child node and the list.

## Iterative Approach using a Stack
As a follow-up to the recursive solution, we can perform the preorder traversal iteratively using an explicit stack. This approach avoids the risk of stack overflow for very deep trees by managing the traversal process on the heap instead of the call stack.
**Time:** O(N), where N is the total number of nodes. Each node is pushed onto and popped from the stack exactly once. · **Space:** O(W), where W is the maximum width of the tree. In the worst case, for a complete N-ary tree, the last level can contain roughly N nodes, leading to a space complexity of O(N). This space is used by the explicit stack.
**Pros:** Avoids `StackOverflowError` that can occur with deep trees in the recursive approach.; Can be more memory efficient in certain tree structures (e.g., a completely skewed tree where its space complexity would be O(1) while recursion's would be O(N)).
**Cons:** The logic can be slightly less intuitive than the recursive version, particularly the need to push children onto the stack in reverse order.; Requires manual management of the stack.
### Explanation
The core idea is to use a stack to simulate the function call stack used in recursion. We start by pushing the root node onto the stack. Then, we enter a loop that continues as long as the stack is not empty. In each iteration, we pop a node, add its value to our result list, and then push its children onto the stack. A key detail is that we must push the children from right to left. This ensures that the leftmost child is at the top of the stack and will be processed next, correctly maintaining the preorder sequence.

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

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

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

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

        Stack<Node> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            Node node = stack.pop();
            result.add(node.val);

            // Push children from right to left to process them from left to right
            for (int i = node.children.size() - 1; i >= 0; i--) {
                stack.push(node.children.get(i));
            }
        }

        return result;
    }
}
```
### Algorithm
*   Initialize an empty `List<Integer>` for the results and an empty `Stack<Node>`.
*   If the `root` is `null`, return the empty list.
*   Push the `root` node onto the stack.
*   Loop as long as the stack is not empty:
    1.  Pop a node from the top of the stack. Let's call it `currentNode`.
    2.  Add the value of `currentNode` to the result list.
    3.  Get the list of children for `currentNode`.
    4.  Iterate through the children in **reverse order** (from right to left).
    5.  Push each child onto the stack. Pushing in reverse order ensures that when we pop them, they are processed in the correct left-to-right order.
*   Return the result list.

# Solutions
### Java

```java
/* // Definition for a Node. class Node { public int val; public List<Node> children; public Node() {} public Node(int _val) { val = _val; } public Node(int _val, List<Node> _children) { val = _val; children = _children; } }; */ class Solution { public List < Integer > preorder ( Node root ) { if ( root == null ) { return Collections . emptyList (); } List < Integer > ans = new ArrayList <>(); Deque < Node > stk = new ArrayDeque <>(); stk . push ( root ); while (! stk . isEmpty ()) { Node node = stk . pop (); ans . add ( node . val ); List < Node > children = node . children ; for ( int i = children . size () - 1 ; i >= 0 ; -- i ) { stk . push ( children . get ( i )); } } return ans ; } }
```

### CPP

```cpp
/* // Definition for a Node. class Node { public: int val; vector<Node*> children; Node() {} Node(int _val) { val = _val; } Node(int _val, vector<Node*> _children) { val = _val; children = _children; } }; */ class Solution { public: vector < int > preorder ( Node * root ) { if ( ! root ) return {}; vector < int > ans ; stack < Node *> stk ; stk . push ( root ); while ( ! stk . empty ()) { Node * node = stk . top (); ans . push_back ( node -> val ); stk . pop (); auto children = node -> children ; for ( int i = children . size () - 1 ; i >= 0 ; -- i ) stk . push ( children [ i ]); } return ans ; } };
```

### Python

```python
""" # Definition for a Node. class Node: def __init__(self, val=None, children=None): self.val = val self.children = children """ class Solution : def preorder ( self , root : 'Node' ) -> List [ int ]: ans = [] if root is None : return ans stk = [ root ] while stk : node = stk . pop () ans . append ( node . val ) for child in node . children [:: - 1 ]: stk . append ( child ) return ans
```