Average of Levels in Binary Tree
Last Updated: April 3, 2026
Understanding the Problem
We have a binary tree and we need to compute the average of all node values at each depth level. Level 0 is the root, level 1 is the root's children, level 2 is the grandchildren, and so on.
The word "each level" is the key here. We are not computing a single average over the whole tree. We need to group nodes by their depth, compute a separate average for each group, and return those averages in order from top to bottom.
This naturally leads us to think about level-order traversal. If we can process all nodes at the same depth together, computing averages becomes straightforward: sum the values, divide by the count. The question is just how we group them, and there are two clean ways to do it.
Key Constraints:
1 <= number of nodes <= 10^4-> With up to 10,000 nodes, O(n) and O(n log n) approaches are both fine. Even O(n^2) would work within limits, but there is no reason to go there.-2^31 <= Node.val <= 2^31 - 1-> Node values can be as large as Integer.MAX_VALUE or as small as Integer.MIN_VALUE. If we sum multiple such values, we can overflow a 32-bit integer. We need to uselong(or equivalent) for the running sum at each level.
Approach 1: BFS (Level-Order Traversal)
Intuition
The most natural way to compute averages per level is to process the tree level by level. BFS does exactly this. We use a queue, and at each step, we know how many nodes are in the current level (it is the current size of the queue). We dequeue all of them, sum their values, count them, and compute the average. Then we enqueue their children, which form the next level.
The trick that makes BFS work level-by-level is capturing the queue size at the start of each level. Before we start dequeuing, we check how many nodes are in the queue right now. That number tells us exactly how many nodes belong to the current level. We process exactly that many, and anything we enqueue during processing belongs to the next level.
BFS naturally visits nodes in level order. The key insight is using the queue size at the start of each iteration to know exactly how many nodes belong to the current level. Everything we enqueue during that iteration belongs to the next level, so there is a clean separation between levels without needing any extra markers or sentinel values.
The queue only ever holds at most two consecutive levels of nodes. For a balanced binary tree, the widest level has about n/2 nodes, so the queue peaks at roughly n/2 elements. For a skewed tree, the queue holds just 1 node at a time.
Algorithm
- If the root is null, return an empty list.
- Initialize a queue and add the root to it.
- While the queue is not empty:
- Record the current size of the queue. This is the number of nodes at this level.
- Initialize a running sum (using a long to avoid overflow).
- Dequeue exactly that many nodes, adding each node's value to the sum and enqueuing its non-null children.
- Compute the average as sum divided by count, and add it to the result list.
- Return the result list.
Example Walkthrough
Code
- Time Complexity: O(n). We visit every node in the tree exactly once. For each node, the work is O(1): add its value to the sum and enqueue its children.
- Space Complexity: O(w) where w is the maximum width of the tree. The queue holds at most one full level at a time. For a complete binary tree, the last level has roughly n/2 nodes, so w is O(n) in the worst case. For a skewed tree, w is O(1).
BFS is already optimal in terms of time, but the queue can hold up to half the tree in memory for wide trees. What if we tracked level information during a DFS instead, using only O(h) stack space?
Approach 2: DFS (Depth-First Search)
Intuition
DFS does not process nodes level by level, but it does know the depth of every node it visits. If we pass the current depth along during recursion, we can accumulate the sum and count for each level in two parallel arrays. After the DFS finishes, we just divide each level's sum by its count to get the average.
Think of it this way: BFS groups nodes by level explicitly through the queue. DFS groups them implicitly by tagging each node with its depth and using that depth as an index into our tracking arrays. The end result is the same, but the traversal order is different.
This approach shines when the tree is very tall and narrow (like a skewed tree), because the call stack depth is O(h) and h could be much smaller than the queue width in BFS.
DFS visits every node exactly once, just like BFS. Since we tag each node with its depth and accumulate into level-indexed arrays, the order of visits does not matter. Whether we visit node 9 before or after node 20 is irrelevant because both contribute to level 1's sum and count.
The depth == sums.size() check is a neat trick. Because DFS goes left-first and top-down, the first time we reach any given depth is always through the leftmost path. So the sums and counts lists grow in order, and we never skip a depth.
Algorithm
- Create two lists:
sumsto store the running sum at each level, andcountsto store the number of nodes at each level. - Run a DFS starting from the root at depth 0.
- At each node:
- If the current depth equals the size of
sums, this is the first time we have reached this depth. Append the node's value tosumsand 1 tocounts. - Otherwise, add the node's value to
sums[depth]and incrementcounts[depth]. - Recurse on the left child with depth + 1.
- Recurse on the right child with depth + 1.
- After DFS completes, build the result by dividing
sums[i]bycounts[i]for each level.
Example Walkthrough
Code
- Time Complexity: O(n). We visit every node exactly once. At each node, we do O(1) work (add to sum, increment count). The final pass to compute averages is O(d) where d is the depth, which is at most n.
- Space Complexity: O(h) where h is the height of the tree. The recursion call stack goes as deep as the tree height. For a balanced tree, h is O(log n). For a completely skewed tree, h is O(n). The sums and counts arrays use O(d) space, dominated by the recursion stack.