Description:
Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array.
Solution:
Time Complexity : O(n)
Space Complexity: O(n)
/// Breadth first search approach
// Traverse the tree and at each level add to a sum variable that counts the total at each level
// After counting the total at each level use the length of the queue to find the average at that level
var averageOfLevels = function(root) {
const queue = [];
const averagePerLevel = [];
queue.push(root);
while(queue.length) {
let sum = 0;
// Save the length value to calculate the average after getting the sum of all values in at that level
let levelLength = queue.length;
for(let i = 0; i < levelLength; i++) {
let node = queue.shift();
sum += node.val;
if(node.left) queue.push(node.left)
if(node.right) queue.push(node.right)
}
averagePerLevel.push(sum / levelLength)
}
return averagePerLevel;
};
Top comments (0)