Given the root of an N-ary tree, return the level order traversal of its nodes’ values. Level order traversal means visiting all nodes at each level from left to right before moving on to the next level.
Table of Contents
Sample Input:
N-ary Tree:
1
/ | \
3 2 4
/ \
5 6
Expected Output:
[
[1],
[3, 2, 4],
[5, 6]
]
The level order traversal of the N-ary tree will give a 2D vector with nodes’ values grouped by level.
Time and Space Complexity:
The time complexity of the algorithm is O(n), where ‘n’ is the number of nodes in the N-ary tree. We need to visit each node once to perform the level order traversal. The space complexity is O(w), where ‘w’ is the maximum width of the N-ary tree (i.e., the maximum number of nodes at any level). In the worst case, the space required to store the nodes at the last level can be at most the width of the tree.
C++ solution:
#include <iostream>
#include <vector>
#include <queue>
// Definition for a node of an N-ary tree.
class Node {
public:
int val;
std::vector<Node*> children;
Node() {}
Node(int _val) {
val = _val;
}
Node(int _val, std::vector<Node*> _children) {
val = _val;
children = _children;
}
};
std::vector<std::vector<int>> levelOrder(Node* root) {
std::vector<std::vector<int>> result;
// Base case: if the root is null, return an empty result
if (root == nullptr) {
return result;
}
// Create a queue to perform level order traversal
std::queue<Node*> nodeQueue;
nodeQueue.push(root);
// Perform level order traversal
while (!nodeQueue.empty()) {
int levelSize = nodeQueue.size();
std::vector<int> currentLevel;
// Process all nodes at the current level
for (int i = 0; i < levelSize; ++i) {
Node* node = nodeQueue.front();
nodeQueue.pop();
currentLevel.push_back(node->val);
// Enqueue all children of the current node
for (Node* child : node->children) {
nodeQueue.push(child);
}
}
// Add the current level to the result
result.push_back(currentLevel);
}
return result;
}
int main() {
// Construct the N-ary tree for the sample input
Node* root = new Node(1);
root->children.push_back(new Node(3));
root->children.push_back(new Node(2));
root->children.push_back(new Node(4));
root->children[0]->children.push_back(new Node(5));
root->children[0]->children.push_back(new Node(6));
// Perform the level order traversal of the N-ary tree
std::vector<std::vector<int>> levelOrderResult = levelOrder(root);
// Print the result
std::cout << "Level Order Traversal:" << std::endl;
for (const auto& level : levelOrderResult) {
std::cout << "[";
for (int i = 0; i < level.size(); ++i) {
std::cout << level[i];
if (i < level.size() - 1) {
std::cout << ", ";
}
}
std::cout << "]" << std::endl;
}
// Don't forget to free the allocated memory
// ...
return 0;
}
The levelOrder function performs the level order traversal of the N-ary tree using a queue. It starts from the root node, and at each level, it processes all nodes at that level by adding them to the currentLevel vector and enqueuing all their children. It continues this process until the queue becomes empty, and all levels are processed.
In the given example, the function will correctly perform the level order traversal of the N-ary tree, and the output will be as follows:
Level Order Traversal:
[1]
[3, 2, 4]
[5, 6]
The time complexity is O(n) as we need to visit each node once, and the space complexity is O(w) due to the maximum width of the N-ary tree, where ‘w’ is the maximum number of nodes at any level.