Whole-Number Average of Every Level
Solve this ProblemYou are given the root of a binary tree whose node values are non-negative integers. For every level of the tree, from the root level down, compute the average of the values on that level and round it down to a whole number. Return these averages as a list, one per level.
Collecting the values of every level first works. Going level by level with a queue lets you keep just one running sum at a time.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
0 ≤ number of nodes ≤ 100 - ◆
0 ≤ node.val ≤ 1000 (values are never negative, so rounding down is unambiguous) - ◆
The tree is given as its root node (null for an empty tree); each node has a val, a left child and a right child - ◆
For each level of the tree, from the root level downwards, return the average of its values ROUNDED DOWN to a whole number (for example an average of 6.67 becomes 6). An empty tree gives an empty list
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Collect Each Level's Values, Then Average
BruteWalk the tree recursively while remembering the depth; a list of levels is grown as new depths are met, and every node's value is appended to the list for its depth. After the walk, add up each stored list and divide by its length (integer division rounds down for non-negative values). Left before right keeps each level in order, though the order does not matter for an average. It is O(n) time but stores every value again, so it needs O(n) extra space.
O(n)O(n)1class Solution {
2 public List<Integer> levelAverages(TreeNode root) {
3 List<List<Integer>> levels = new ArrayList<>();
4 group(root, 0, levels);
5 List<Integer> result = new ArrayList<>();
6 for (List<Integer> level : levels) {
7 int sum = 0;
8 for (int v : level) sum += v;
9 result.add(sum / level.size());
10 }
11 return result;
12 }
13
14 private void group(TreeNode node, int depth, List<List<Integer>> levels) {
15 if (node == null) return;
16 if (levels.size() == depth) levels.add(new ArrayList<>());
17 levels.get(depth).add(node.val);
18 group(node.left, depth + 1, levels);
19 group(node.right, depth + 1, levels);
20 }
21}Optimal — Breadth-First, Keep Only a Running Sum per Level
OptimalProcess the tree level by level with a queue. Before each round, the queue size is exactly the number of nodes on the level. Take that many nodes off the front, add their values into a single running sum, and queue their children for the next level. Then the level's average is sum / size (rounded down). Nothing is stored except the current sum, and the queue holds at most about two levels: O(n) time, O(w) extra space where w is the widest level.
O(n)O(w)1class Solution {
2 public List<Integer> levelAverages(TreeNode root) {
3 List<Integer> result = new ArrayList<>();
4 if (root == null) return result;
5 Queue<TreeNode> queue = new ArrayDeque<>();
6 queue.add(root);
7 while (!queue.isEmpty()) {
8 int size = queue.size();
9 int sum = 0;
10 for (int i = 0; i < size; i++) {
11 TreeNode node = queue.poll();
12 sum += node.val;
13 if (node.left != null) queue.add(node.left);
14 if (node.right != null) queue.add(node.right);
15 }
16 result.add(sum / size);
17 }
18 return result;
19 }
20}