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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public List<Integer> preorder(Node root) {
  List<Integer> result = new LinkedList<>();
  preorder(root, result);
  return result;
}

private void preorder(Node root, List<Integer> result) {
  if (root == null) {
    return;
  }
  result.add(root.val);
  for (Node n : root.children) {
    preorder(n, result);
  }    
}

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public List<Integer> preorder(Node root) {
  List<Integer> result = new LinkedList<>();
  if (root == null) {
    return result;
  }
  Stack<Node> stack = new Stack<>();
  stack.push(root);

  while (stack.size() > 0) {
    Node curr = stack.pop();
    result.add(curr.val);     // visit
    int n = p.children.size();
    for (int i = n - 1; i >= 0; --i) { // from right to left
      stack.push(p.children.get(i)); // guarantee not null
    }
  }
  return result;
}

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
2
3
4
// only have two levels
        5
     / ... \     
2  4  3  6  1  9  (n - 1)

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.