Average of Levels in Binary Tree

Problem Statement

In this task, you are given the root of a binary tree. Your goal is to compute the average value of the nodes at each level of the tree and return these averages as an array. The average for each level should be accurately calculated to a precision where deviations of up to 10^-5 from the actual average are considered acceptable. This problem tests your understanding of tree traversal techniques and how to manage data at different tree levels.

Examples

Example 1

Input:

root = [3,9,20,null,null,15,7]

Output:

[3.00000,14.50000,11.00000]
Explanation: The average value of nodes on level 0 is 3, on level 1 is 14.5, and on level 2 is 11.
Hence return [3, 14.5, 11].

Example 2

Input:

root = [3,9,20,15,7]

Output:

[3.00000,14.50000,11.00000]

Constraints

• The number of nodes in the tree is in the range [1, 104].
• -231 <= Node.val <= 231 - 1

Approach and Intuition

1. To solve this problem, you’ll need to traverse through each level of the binary tree. The best strategy for this is using the Breadth-First Search (BFS) technique. This approach involves using a queue to keep track of nodes at the current level and to access their children.

2. Here's the plan:

   1. Start with the root node and initialize a queue.
   2. For each level:
      • Calculate the total of the node values and count the nodes to derive the average for that level.
      • Append all children of the nodes at the current level to the queue.
   3. Proceed to compute the average and move to the next level.

3. This method ensures that each node and its children are visited in level order, making the computation of averages straightforward.

The idea is simple but efficient, leveraging the nature of BFS to access each level's nodes in sequence and performing the necessary calculations for the average. Despite the large range of possible node values and tree sizes as highlighted in the constraints section, the BFS approach efficiently handles the tree level by level, ensuring that memory and computation are managed properly.

Solutions

public class Solution {
    public List<Double> levelAverages(TreeNode rootNode) {
        List<Double> averages = new ArrayList<>();
        Queue<TreeNode> currentLevel = new LinkedList<>();
        currentLevel.add(rootNode);
        
        while (!currentLevel.isEmpty()) {
            long levelSum = 0, levelCount = 0;
            Queue<TreeNode> nextLevel = new LinkedList<>();
            
            while (!currentLevel.isEmpty()) {
                TreeNode node = currentLevel.poll();
                levelSum += node.val;
                levelCount++;
                if (node.left != null)
                    nextLevel.add(node.left);
                if (node.right != null)
                    nextLevel.add(node.right);
            }
            
            currentLevel = nextLevel;
            averages.add((double) levelSum / levelCount);
        }
        return averages;
    }
}