#637 Average of Levels in Binary Tree
the problem
In plain words
Return the average of the node values on each level, top level first. Answers within 10⁻⁵ of the exact value are accepted.
in root = [3,9,20,null,null,15,7]
out [3.00000,14.50000,11.00000]
Level 1 is (9 + 20) / 2 = 14.5; level 2 is (15 + 7) / 2 = 11.
in root = [3,9,20,15,7]
out [3.00000,14.50000,11.00000]
- 1 ≤ number of nodes ≤ 10⁴
- -2³¹ ≤ Node.val ≤ 2³¹ − 1
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternTree BFS (level order)
It's Level Order Traversal with a sum instead of a list. The only traps are Java ones: two values of 2³¹ − 1 overflow an int sum, and sum / size on integers throws away the .5.
solutions
From brute force to optimal
Preorder walk carrying the depth; add each value into sums[depth] and count[depth], divide at the end.
- walk(node, depth): on a new depth, open sum 0 and count 0.
- sums[depth] += val; counts[depth]++.
- Recurse left and right with depth + 1.
- Average = (double) sum / count per depth.
One visit per node, then one division per level.
Recursion stack plus two small lists with one entry per level.
class Solution { public List<Double> averageOfLevels(TreeNode root) { List<Long> sums = new ArrayList<>(); List<Integer> counts = new ArrayList<>(); walk(root, 0, sums, counts); List<Double> averages = new ArrayList<>(); for (int d = 0; d < sums.size(); d++) averages.add((double) sums.get(d) / counts.get(d)); return averages; } private void walk(TreeNode node, int depth, List<Long> sums, List<Integer> counts) { if (node == null) return; if (depth == sums.size()) { // first node we meet at this depth sums.add(0L); counts.add(0); } sums.set(depth, sums.get(depth) + node.val); counts.set(depth, counts.get(depth) + 1); walk(node.left, depth + 1, sums, counts); walk(node.right, depth + 1, sums, counts); }}Size-snapshot BFS; add up the level while polling it, then divide.
- Offer root.
- Each round: size = queue.size(); long sum = 0.
- Poll size nodes, add each value, offer children.
- Add (double) sum / size.
Each node offered and polled once.
The queue holds one level at a time.
class Solution { public List<Double> averageOfLevels(TreeNode root) { List<Double> averages = new ArrayList<>(); Deque<TreeNode> queue = new ArrayDeque<>(); queue.offer(root); // the tree always has at least one node while (!queue.isEmpty()) { int size = queue.size(); long sum = 0; // two values of 2³¹ − 1 already overflow an int for (int i = 0; i < size; i++) { TreeNode node = queue.poll(); sum += node.val; if (node.left != null) queue.offer(node.left); if (node.right != null) queue.offer(node.right); } averages.add((double) sum / size); // cast BEFORE dividing, or 29 / 2 = 14 } return averages; }}in the room
How to say it in the interview
talk track
- Say: "this is level order, keeping a sum per level".
- Call out the
longsum and the double division before you write them — that's what this problem is testing.
traps
int sumoverflows: a level holding 2147483647 twice comes out negative.sum / sizewith two integers: 29 / 2 = 14. Cast first:(double) sum / size.
what they ask next
Follow-ups
Largest value in each row (LC 515)?
Same loop; keep a running max per level instead of a sum (start it at the first polled value, or Integer.MIN_VALUE).
Level with the maximum sum (LC 1161)?
Same loop; remember the best sum and its 1-based level number.
before you submit
Edge cases to test
- One node → [its value, as a double].
- Two values of 2³¹ − 1 on one level: an
intsum overflows — uselong. - Odd sums: (9 + 20) / 2 must be 14.5, not 14.
practise next
Similar problems
- #102Binary Tree Level Order TraversalMediumin Traversals
- #103Binary Tree Zigzag Level Order TraversalMediumin Traversals