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 useCollections.reverse()
to reverse it rather than usingget
, 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.