# N-ary Tree Preorder Traversal- Easy

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

Given 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?

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

**Constraints:**

- The height of the n-ary tree is less than or equal to
`1000`

- The total number of nodes is between
`[0, 10^4]`

**Solution:**

Based on preorder traversals : https://takeitoutamber.medium.com/tree-recursive-traversals-e5fdfc17e646

Code:

"""

# 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]:

stack = [root]

res = []

while stack:

node = stack.pop()

if node:

res.append(node.val)

# Instead of appending one child at a time,

# extend the stack -> its 30% more faster.ArithmeticError

# push the children from right to left

stack.extend(node.children[::-1])

# for x in node.children[::-1]:

# stack.append(x)

return res

Runtime: 52 ms, faster than 80.81% of Python3 online submissions for N-ary Tree Preorder Traversal.

Memory Usage: 16.2 MB, less than 15.47% of Python3 online submissions for N-ary Tree Preorder Traversal.

- 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)O(*N*), where N*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)O(
*N*).

## Recursive solution -> slower than the iterative solution

`class Solution:`

def __init__(self):

self.res = []

def preorder(self, root: 'Node') -> List[int]:

if root:

self.res.append(root.val)

for child in root.children:

self.preorder(child)

return self.res

Runtime: 56 ms, faster than 24.60% of Python3 online submissions for N-ary Tree Preorder Traversal.

Memory Usage: 16.1 MB, less than 15.68% of Python3 online submissions for N-ary Tree Preorder Traversal.