Given the root of a binary tree, return the average value of the nodes on each level of the tree.
Table of Contents
Sample Input:
Tree:
3
/ \
9 20
/ \
15 7
Expected Output:
[3.00000, 14.50000, 11.00000]
In this example, the average value of nodes on each level of the binary tree will be calculated and returned as an array of floating-point values.
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<double> averageOfLevels(TreeNode* root) {
std::vector<double> 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();
double levelSum = 0.0;
// Process all nodes at the current level
for (int i = 0; i < levelSize; ++i) {
TreeNode* node = nodeQueue.front();
nodeQueue.pop();
levelSum += 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);
}
}
// Calculate the average value for the current level
double levelAverage = levelSum / levelSize;
// Add the average value to the result
result.push_back(levelAverage);
}
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);
// Calculate the average of levels in the binary tree
std::vector<double> averageOfLevelsResult = averageOfLevels(root);
// Print the result
std::cout << "Average of Levels:" << std::endl;
for (const auto& average : averageOfLevelsResult) {
std::cout << average << ", ";
}
std::cout << std::endl;
// Don't forget to free the allocated memory
// ...
return 0;
}
The averageOfLevels 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 calculating the sum of their values and the number of nodes. Then, it calculates the average value for the current level and adds it to the result vector.
In the given example, the function will correctly calculate the average of levels in the binary tree, and the output will be as follows:
Average of Levels:
3,
14.5,
11,