The O(n) Club: Average of Levels in a Binary Tree (Or Why Java Hates Decimals)

The O(n) Club: Average of Levels in a Binary Tree (Or Why Java Hates Decimals)

⚡ TL;DR

For each level of your binary tree, don’t overthink it: use BFS with a queue, sum the nodes, divide by how many show up, and throw those averages in a new list. Beware of Java’s integer division, or your answers will be duller than a padded meeting.

// One-loop BFS flavor
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
    int levelSize = queue.size();
    double levelSum = 0;
    for (int i = 0; i < levelSize; i++) {
        TreeNode node = queue.poll();
        levelSum += node.val;
        if (node.left != null) queue.add(node.left);
        if (node.right != null) queue.add(node.right);
    }
    averages.add(levelSum / levelSize);
}

🧠 How Devs Usually Mess This Up

Classic mistake? Using DFS. Suddenly you’re juggling lists, levels, and more bugs than a hackathon at a mosquito farm. Some assume every tree level’s as fat as the root—nah, not unless you planted it in SimCity. And if you trust int/int for division? Well… hope you like answers that are always too low.

🔍 What’s Actually Going On

Imagine a company org chart, but every department’s a jungle. To get the average salary per level, you round up everyone on each floor (BFS), total their paychecks, and divide by headcount. You don’t try to snake through branches hoping you wind up at every desk—DFS makes that a bureaucratic nightmare. Instead, BFS keeps it clean and organized, just like IT wishes your desktop was.

🛠️ PseudoCode

• Start a queue with the root node.
  Queue<TreeNode> queue = new LinkedList<>(); queue.add(root);—like the line at the DMV, only faster.
• While the queue isn’t empty: Record the levelSize (people on this ‘floor’). Prepare calculator.
• For every node this level: Remove from queue, sum value, queue its kids if not null. You’re counting candy in each jar.
• After the loop: averages.add(sum / levelSize). If you forgot double, say hello to integer rounding disaster.
• Repeat until you’ve seen every level, or run out of caffeine.

💻 The Code

// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}
 import java.util.*;
 public class BinaryTreeAverages {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> result = new ArrayList<>();
        if (root == null) return result;
         Queue<TreeNode> 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);
            }
            result.add(sum / levelSize);
        }
        return result;
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Unbalanced trees: Some levels have a single awkward loner. Don’t hardcode node counts—or you’ll be ghosting the edge cases.
• Integer division: If your average is 1 instead of 1.5, guess what? int/int == int. Cast before you crash.
• Null children: Queuing a null node is like inviting a ghost to your standup—it just confuses everyone.
• Complexity: You touch each node once (O(n) time) and max queue holds the widest tree level. Not your usual O(1) fantasy.

🧠 Interviewer Brain-Tattoo

Don’t BFS with DFS unless you enjoy debugging existential crises. Level order means level order. Coffee, queue, repeat.