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)

Examples

Example 1:

graph TD
  1 --- A[3] & B[2] & C[4]
  A --- 5 & 6

(have to use A, B, C in mermaid to make the ordering of nodes better)

1
2

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

Example 2:

graph TD
  1 --- 2 & 3 & 4 & 5
  3 --- 6 & 7
  7 --- 11
  11 --- 14
  4 --- 8
  8 --- 12
  5 --- 9 & 10
  9 --- 13
  
1
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]

Solution

Method 1 - DFS

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

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

	helper(root, ans);

	return ans;
}

private void helper(Node root, List<Integer> ans) {
	ans.add(root.val);
	for (Node node : root.children) {
		helper(node, ans);
	}
}

Complexity

  • Time: O(N) - where N is number of nodes
  • Space: O(1)