Reference: LeetCode

Difficulty: Easy

## Problem

Given an n-ary tree, return the preorder traversal of its nodes’ values.

**Example:**

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

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

## Analysis

### Recursion

1 | public List<Integer> preorder(Node root) { |

**Time:** $O(N)$**Space:** $O(h)$

### Iteration

**Note:**

- Notice that if the children list is implemented with
`LinkedList`

, we’d better use`Collections.reverse()`

to reverse it rather than using`get`

, which might take $O(N^2)$ runtime in the worst case. - Also notice that
`children`

list is guaranteed to be not null, and no element is null too.

1 | public List<Integer> preorder(Node root) { |

**Time:** $O(N)$**Space:** $O(N)$. As for N-ary trees, the iteration method’s runtime is determined by the maximum number of nodes at any level. See the worst case example below (also consider the result list).

The worst case of space is as follows:

1 | // only have two levels |

First level contains only the root, while all other nodes lie in the second level. So we need to push all the nodes in the list.