Average of Levels in Binary Tree

Average of Levels in Binary Tree

What is this problem about?

The Average of Levels in Binary Tree interview question asks you to traverse a binary tree level by level and calculate the average value of nodes at each level. The result should be an array of these averages. This Average of Levels in Binary Tree coding problem is a classic application of Level Order Traversal.

Why is this asked in interviews?

Companies like Meta and Amazon use this to check if a candidate understands Breadth-First Search (BFS) in trees. It's a standard problem that tests your ability to use a Queue to manage nodes level-by-level and correctly handle the sum and count of elements at each depth.

Algorithmic pattern used

This follows the Breadth-First Search, Depth-First Search, Binary Tree, Tree interview pattern. While DFS can work (by passing depth as an argument), BFS is more intuitive. You use a queue to store nodes. For each level, you determine the number of nodes currently in the queue, process them all, sum their values, and calculate the average before moving to the next level.

Example explanation

Binary Tree:

    3
   / 
  9  20
    /  
   15   7

• Level 0: Node 3. Average = 3/1 = 3.
• Level 1: Nodes 9 and 20. Sum = 29, Count = 2. Average = 14.5.
• Level 2: Nodes 15 and 7. Sum = 22, Count = 2. Average = 11. Result: [3, 14.5, 11].

Common mistakes candidates make

• Incorrect Level Tracking: Forgetting to "freeze" the queue size at the start of each level, causing the loop to accidentally process nodes from the next level in the current sum.
• Integer Division: Performing integer division (e.g., 29 / 2 = 14) when the result should be a float (14.5).
• Empty Tree: Not handling the case where the root is null.

Interview preparation tip

Always use a Queue for level-order traversal. Remember the pattern: size = queue.length; for(i=0; i < size; i++) { ... }. This ensures you process exactly one level at a time.