Back to Beginner: I/O, Arithmetic, Loops
Q13Question 13 of 30

Level Averages in a Binary Tree (Average Value per Level)

Key Concepts
  • Use BFS with the level-size snapshot pattern: record queue size at the start of each level, drain that many nodes, then move to the next level.
  • For each level, accumulate a running sum of node values and divide by the level size to produce one average per level.
  • For financial values use BigDecimal for the sum and divide with an explicit scale and RoundingMode to avoid ArithmeticException.
  • Using double for money introduces binary floating-point error that is unacceptable in banking.
  • Time is O(n) visiting every node once; space is O(w) where w is the maximum width of any level.
  • The level-size snapshot is reusable for level order traversal, level max, level min, and zigzag traversal.

Definition

BFS per level, sum the values, divide by the level size, one average per level.
  • BFS level-size snapshot – record queue.size() at the start of each level; drain that many nodes, enqueuing children as you go.
  • Level average – accumulate a running sum across the level and divide by the level size.
  • Money safety – use BigDecimal for the sum and divide with sum.divide(count, 2, RoundingMode.HALF_UP).
  • Complexity – O(n) time visiting each node once; O(w) space for the queue, where w is the maximum level width.

National Bank of India wants the average approval limit at each rank of its hierarchy tree. The system adds up every approver's limit on a rank and divides by how many approvers are on that rank, producing one average per rank from top to bottom.

Understanding the Concepts

What is the problem?

Given the root of a binary tree, return a list of averages, one per level, from top to bottom. Level 0 is the root, level 1 is its children, and so on.

How do you implement it with BFS?

JAVA
package com.bank.service;

import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.*;

public class LevelAverageCalculator {

    static class TreeNode {
        BigDecimal limit;
        TreeNode left, right;
        TreeNode(BigDecimal limit) { this.limit = limit; }
    }

    public static List<BigDecimal> levelAverages(TreeNode root) {
        List<BigDecimal> averages = new ArrayList<>();
        if (root == null) return averages;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int levelSize = queue.size(); // snapshot
            BigDecimal levelSum = BigDecimal.ZERO;

            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                levelSum = levelSum.add(node.limit);
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }

            BigDecimal avg = levelSum.divide(
                new BigDecimal(levelSize), 2, RoundingMode.HALF_UP
            );
            averages.add(avg);
        }
        return averages;
    }

    public static void main(String[] args) {
        // Approval hierarchy at National Bank of India
        TreeNode root = new TreeNode(new BigDecimal("500000"));
        root.left = new TreeNode(new BigDecimal("200000"));
        root.right = new TreeNode(new BigDecimal("300000"));
        root.left.left = new TreeNode(new BigDecimal("50000"));
        root.left.right = new TreeNode(new BigDecimal("100000"));
        root.right.right = new TreeNode(new BigDecimal("150000"));

        System.out.println("Level averages: " + levelAverages(root));
    }
}
TEXT
Level averages: [500000.00, 250000.00, 100000.00]

Why use BigDecimal instead of double?

Double introduces binary floating-point error. For example, 0.1 + 0.2 in double is 0.30000000000000004. When averaging rupee amounts across hundreds of nodes, the error accumulates. BigDecimal stores values exactly and divides with an explicit scale and rounding mode, so the average is deterministic and never throws an ArithmeticException for non-terminating decimals.

What is the level-size snapshot pattern?

At the start of each level iteration, you record queue.size(). That snapshot tells you exactly how many nodes belong to the current level. You drain that many nodes (adding their children for the next level), and when the inner loop finishes, the queue holds only next-level nodes. This pattern is reused for level-order max, min, zigzag, and right-side view.

What are edge cases?

  • Null root: return an empty list.
  • Single node: one level with one average, which is the root's value.
  • Skewed tree (all left children): each level has one node, so the average equals that node's value.

What are common mistakes?

JAVA
// Wrong: dividing BigDecimal without scale and rounding
levelSum.divide(new BigDecimal(levelSize)); // ArithmeticException if non-terminating!

// Correct: specify scale and rounding
levelSum.divide(new BigDecimal(levelSize), 2, RoundingMode.HALF_UP);

How does this generalize to other level aggregations?

  • The same BFS skeleton supports any per-level aggregation:
  • Level max: track the maximum value instead of summing.
  • Level min: track the minimum.
  • Level count: just use levelSize.
  • Zigzag: alternate the order of adding to the result list.

What should a senior engineer know?

Specifying both scale and rounding mode is the mark of production financial code. Using double for money in a banking system is a bug waiting to happen. A senior engineer defines the rounding mode as a shared constant across the codebase.

What are common interview follow-up questions?

  • How would you find the level with the largest average?
  • Can you compute level averages with DFS instead of BFS?
  • How would you handle a tree where nodes have null values?

Visual Overview

DIAGRAM
         500000
        /      \
    200000    300000
    /    \        \
  50000  100000  150000

  Level 0: [500000]         → avg = 500000.00
  Level 1: [200000, 300000] → avg = 250000.00
  Level 2: [50000, 100000, 150000] → avg = 100000.00

Key Takeaway

Computing the average value on each level of a binary tree is standard BFS with the level-size snapshot pattern. Instead of collecting values, you accumulate a running sum across each level and divide by the snapshot size to get one average per level. The traversal mechanics are identical to plain level-order: a FIFO queue, the size snapshot at the start of each level, and enqueuing children while draining.

Because this is banking data, the accumulation and division use BigDecimal rather than double. Double introduces binary floating-point error that is unacceptable for money. The division specifies an explicit scale and rounding mode, because dividing a BigDecimal without rounding throws an ArithmeticException on a non-terminating quotient.

In a project at National Bank of India, this backed a delegation-of-authority monitor. Each node in the approval tree carried a rupee approval limit, and risk wanted the average limit at each rank from the top down to spot ranks where delegated authority was drifting too high. BFS per level with BigDecimal arithmetic produced those per-rank averages reliably.

Remember one sentence: BFS with the level-size snapshot gives one average per level, and for money that average must use BigDecimal with an explicit scale and rounding mode.

---

Share
Use ← → arrow keys to navigate