Given the root of a binary 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:
Tree:
3
/ \
9 20
/ \
15 7
Expected Output:
[
[3],
[9, 20],
[15, 7]
]
In this example, the level order traversal of the binary 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 binary 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 binary 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 binary tree node.
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
std::vector<std::vector<int>> levelOrder(TreeNode* 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<TreeNode*> 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) {
TreeNode* node = nodeQueue.front();
nodeQueue.pop();
currentLevel.push_back(node->val);
// Enqueue the left and right children, if they exist
if (node->left) {
nodeQueue.push(node->left);
}
if (node->right) {
nodeQueue.push(node->right);
}
}
// Add the current level to the result
result.push_back(currentLevel);
}
return result;
}
int main() {
// Construct the binary tree for the sample input
TreeNode* root = new TreeNode(3);
root->left = new TreeNode(9);
root->right = new TreeNode(20);
root->right->left = new TreeNode(15);
root->right->right = new TreeNode(7);
// Perform the level order traversal of the binary 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 binary 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 their left and right children, if they exist. 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 binary tree, and the output will be as follows:
Level Order Traversal:
[3]
[9, 20]
[15, 7]
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 binary tree, where ‘w’ is the maximum number of nodes at any level.