DEV Community

loading...

637. Average of Levels in Binary Tree (javascript solution)

cod3pineapple profile image codingpineapple ・1 min read

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;
};
Enter fullscreen mode Exit fullscreen mode

Discussion (0)

pic
Editor guide