Leetcode 429. N-ary Tree Level Order Traversal

Problem Explanation

Given an n-ary tree, the problem requires you to return its level order traversal of nodes' values. An n-ary tree is a tree data structure in which each node can have no more than n children.

The level order traversal is implemented by breadth-first search (BFS) in which you exhaust all nodes at the current depth or level (i.e., visiting nodes from left to right) before moving onto nodes at the next depth level.

For example, given the following 3-ary tree:

1
2
3    1
4  / | \
5 3  2  4
6/ \
75  6

We would return the following level-order traversal:

1
2
3[
4  [1],    // level 1
5  [3,2,4], // level 2
6  [5,6] // level 3
7]

Approach

The solution approach simply involves the use of BFS to traverse the given n-ary tree. Conveniently, BFS naturally implements level order traversal due to its nature of exhausting all nodes at the current depth level before moving onto nodes at the next depth level.

We use a queue data structure to effectively implement BFS.

Walkthrough

Let’s walk through a BFS on the above tree:

• Start at the root, push it to the queue, and then start the while loop.

• Remove the root node(1) from the front of the queue, add its value to the current level list, and push its children(3, 2, 4) to the end of the queue.

• Since there is no other node in the queue from the root level, end the current level and add the current level list to the result list.

• Now we still have node 3, 2, 4 in the queue, remove node 3 from front of the queue, add its value to the current level list, and push its children(5, 6) to the end of the queue. Do the same thing for node 2 and 4 which have no child. Since there is no other node in the queue from this level, end the current level, and add the current level list to final result.

• Now we move to the next level, we still have node 5, 6 in the queue, do the same thing for both nodes. After processing both nodes, since there is no other node in the queue from this level, end the current level, and add the current level to final result.

• Lastly, return the final result.

Python Solution

1
2python
3from collections import deque
4
5class Solution:
6    def levelOrder(self, root):
7        if not root:
8            return []
9
10        queue = deque([root])
11        traversal = []
12
13        while queue:
14            level_length = len(queue)
15            current_level = []
16
17            for _ in range(level_length):
18                node = queue.popleft()
19                current_level.append(node.val)
20
21                for child in node.children:
22                    queue.append(child)
23
24            traversal.append(current_level)
25
26        return traversal

Java Solution

1
2java
3class Solution {
4    public List<List<Integer> > levelOrder(Node root) {
5        List<List<Integer> > result = new ArrayList<>();
6        if (root == null) return result;
7
8        Queue<Node> queue = new LinkedList<>();
9        queue.offer(root);
10
11        while (!queue.isEmpty()) {
12            List<Integer> level = new ArrayList<>();
13            int size = queue.size();
14            for (int i = 0; i < size; i++) {
15                Node node = queue.poll();
16                level.add(node.val);
17                queue.addAll(node.children);
18            }
19            result.add(level);
20        }
21        return result;
22    }
23}

JavaScript Solution

1
2javascript
3var levelOrder = function(root) {
4    if (!root) {
5        return [];
6    }
7    
8    const queue = [root];
9    const ans = [];
10    
11    while(queue.length > 0) {
12        const currentLevel = [];
13        const length = queue.length;
14        
15        for(let i = 0; i < length; i++) {
16            const node = queue.shift();
17            currentLevel.push(node.val);
18            queue.push(...node.children);
19        }
20        
21        ans.push(currentLevel);
22    }
23    
24    return ans;
25};

C++ Solution

1
2c++
3class Solution {
4public:
5    vector<vector<int>> levelOrder(Node* root) {
6        if (root == nullptr) {
7            return {};
8        }
9
10        vector<vector<int>> ans;
11        queue<Node*> q{{root}};
12
13        while (!q.empty()) {
14            vector<int> currLevel;
15            for (int sz = q.size(); sz > 0; --sz) {
16                Node* node = q.front();
17                q.pop();
18                currLevel.push_back(node->val);
19                for (Node* child : node->children) {
20                    q.push(child);
21                }
22            }
23            ans.push_back(currLevel);
24        }
25
26        return ans;
27    }
28};

C# Solution

1
2csharp
3public class Solution {
4    public IList<IList<int>> LevelOrder(Node root) {
5            
6        List<IList<int> > result = new List<IList<int>>();
7        if (root == null) return result;
8
9        Queue<Node> queue = new Queue<Node>();
10        queue.Enqueue(root);
11
12        while (queue.Count != 0) {
13            List<int> level = new List<int>();
14            int size = queue.Count;
15            for (int i = 0; i < size; i++) {
16                Node node = queue.Dequeue();
17                level.Add(node.val);
18                foreach (Node child in node.children) 
19                    queue.Enqueue(child);
20            }
21            result.Add(level);
22        }
23        return result;
24    }
25}

Each of the above solutions works by first checking if the given root is null, in which case it returns an empty list/array. This serves as the base case for an empty tree.

Subsequently, the solutions create a queue, starting with the root node. Remember, a queue follows a first-in-first-out format. This queue is a key component of the BFS approach.

The idea is to continue processing nodes from the queue until it is empty. For each iteration, the size of the current level of nodes (or, the number of nodes in the queue) is taken. Then each node is processed by adding its value to a list/array of the current level and each of its children is added back into the queue. This is done for the size of each level -- not the entire queue, so we are only iterating through one level at a time. Once all nodes in the current level are processed, this level list/array is added to a final result list/array.

Finally, once the queue is empty, the final list/array is returned. This gives the level order traversal of the given n-ary tree.

The time complexity of these solutions is O(n), as each node is essentially processed once. The space complexity is also O(n), as all nodes might end up being in the queue at the same time (for a perfectly balanced n-ary tree).

Hopefully, this helps you understand how to reliably return the level order traversal of a given n-ary tree. Remember to practice implementing solutions in multiple programming languages.