By Long Luo

This article is the solution Traverse the Tree Level by Level: Standard BFS Solution of Problem 429. N-ary Tree Level Order Traversal.

Intuition

To traverse the tree level by level, we generally use breadth first search. In each round of breadth first search, we will traverse all nodes in the same layer.

For a typical BFS, we put the root node \(\textit{root}\) into the queue fist. In each round of BFS, we first record the number of nodes in the current queue, which is the number of nodes in the upper level.

After that, we remove the front of the queue to take the nodes out of the queue in turn until we get all the nodes of the upper level.

When this round of traversal is completed, we can get all nodes of the current level. In this way, when the BFS is completed, we can get the results.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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

    Queue<Node> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        List<Integer> levelList = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            Node node = queue.poll();
            if (node != null) {
                levelList.add(node.val);
                List<Node> children = node.children;
                for (int j = 0; j < children.size(); j++) {
                    queue.add(children.get(j));
                }
            }
        }

        ans.add(levelList);
    }

    return ans;        
}

Analysis

• Time Complexity: \(O(n)\).
• Space Complexity: \(O(n)\).

All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗