Given the root of a binary tree, return the bottom-up level order traversal of its nodes’ values. The bottom-up level order traversal means visiting all nodes at each level from left to right before moving on to the next level, and then returning the result in reverse order (from bottom to top).
Table of Contents
Sample Input:
Tree:
3
/ \
9 20
/ \
15 7
Expected Output:
[
[15, 7],
[9, 20],
[3]
]
In this example, the bottom-up level order traversal of the binary tree will give a 2D vector with nodes’ values grouped by level, in reverse order.
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>
#include <algorithm>
// 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>> levelOrderBottom(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);
}
// Reverse the result vector to get the bottom-up level order traversal
std::reverse(result.begin(), result.end());
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 bottom-up level order traversal of the binary tree
std::vector<std::vector<int>> levelOrderBottomResult = levelOrderBottom(root);
// Print the result
std::cout << "Bottom-Up Level Order Traversal:" << std::endl;
for (const auto& level : levelOrderBottomResult) {
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;
}
return 0;
}
The levelOrderBottom function performs the bottom-up 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.
After performing the level order traversal, the function reverses the result vector to get the bottom-up level order traversal.
In the given example, the function will correctly perform the bottom-up level order traversal of the binary tree, and the output will be as follows:
Bottom-Up Level Order Traversal:
[15, 7]
[9, 20]
[3]