Dare2Solve
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.
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.
(O(N)), where (N) is the number of nodes in the tree. Each node is processed once.
(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.
class Solution {
public:
vector<double> averageOfLevels(TreeNode* root) {
vector<double> resAverages;
if (!root) return resAverages;
queue<TreeNode*> 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;
}
};
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
class Solution {
public List<Double> averageOfLevels(TreeNode root) {
List<Double> resAverages = new ArrayList<>();
if (root == null) return resAverages;
Queue<TreeNode> 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;
}
}
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;
};