637. Average of Levels in Binary Tree

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

1. Use a queue to perform a BFS traversal of the binary tree.
2. For each level of the tree, sum the values of the nodes and count the number of nodes.
3. Calculate the average by dividing the sum by the count.
4. Append the average to the result list.
5. 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;
};