🎨Now live: Try our Free AI Image Generation Feature

Description
The problem requires us to calculate the average value of nodes on each level of a binary tree. Given a binary tree, return the list of averages for each level.
Intuition
A binary tree can be traversed level-by-level using a breadth-first search (BFS) approach. By summing the values of nodes at each level and then dividing by the number of nodes at that level, we can find the average value for each level.
Approach
- Use a queue to perform a BFS traversal of the binary tree.
- For each level of the tree, sum the values of the nodes and count the number of nodes.
- Calculate the average by dividing the sum by the count.
- Append the average to the result list.
- Continue to the next level until all levels are processed.
Complexity
Time Complexity:
(O(N)), where (N) is the number of nodes in the tree. Each node is processed once.
Space Complexity:
(O(M)), where (M) is the maximum number of nodes at any level in the tree. In the worst case, this could be (O(N/2)) for a complete binary tree.
Code
C++
class Solution {
public:
vector averageOfLevels(TreeNode* root) {
vector resAverages;
if (!root) return resAverages;
queue q;
q.push(root);
while (!q.empty()) {
int levelSize = q.size();
double sum = 0;
for (int i = 0; i < levelSize; ++i) {
TreeNode* node = q.front();
q.pop();
sum += node->val;
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
double avg = sum / levelSize;
resAverages.push_back(avg);
}
return resAverages;
}
};
Python
class Solution:
def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
res_averages = []
if not root:
return res_averages
queue = deque([root])
while queue:
level_size = len(queue)
level_sum = 0
for _ in range(level_size):
node = queue.popleft()
level_sum += node.val
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
avg = level_sum / level_size
res_averages.append(avg)
return res_averages
Java
class Solution {
public List averageOfLevels(TreeNode root) {
List resAverages = new ArrayList<>();
if (root == null) return resAverages;
Queue queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int levelSize = queue.size();
double sum = 0;
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll();
sum += node.val;
if (node.left != null) queue.add(node.left);
if (node.right != null) queue.add(node.right);
}
double avg = sum / levelSize;
resAverages.add(avg);
}
return resAverages;
}
}
JavaScript
function averageOfLevels(root) {
if(!root) return [];
let resAverages = new Array();
let queue = new Array(); // required for tree traversal
queue.push(root);
while(queue.length) {
const next = []; // keeps track of nodes from each level
let sum = 0;
for(const node of queue) {
sum += node.val;
if(node.left) next.push(node.left);
if(node.right) next.push(node.right);
}
const avg = sum / queue.length;
resAverages.push(avg);
// queue has nodes from the next level
queue = next;
}
return resAverages;
};