Average of Levels in Binary Tree
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 phrase "each level" means 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.
Any traversal that can group nodes by depth solves the problem. BFS visits the levels one at a time, so the grouping is direct. DFS can do the same job by recording each node's depth as it descends. Both approaches follow.
Key Constraints:
1 <= number of nodes <= 10^4-> Small enough that any O(n) traversal runs well within limits. Time is not the constraint that matters here.-2^31 <= Node.val <= 2^31 - 1-> A single level can hold thousands of values near the 32-bit limits, so a 32-bit running sum can overflow. Use a 64-bit accumulator. The worst-case sum is about 10^4 x 2^31, roughly 2.1 x 10^13, which a 64-bit integer holds easily and a double-precision float represents exactly (it is below 2^53).
Approach 1: BFS (Level-Order Traversal)
Intuition
BFS processes the tree level by level, which matches the shape of the output. A queue holds the frontier. At the start of each round, the queue contains exactly the nodes of one level, so its size tells us how many nodes to dequeue. We dequeue that many, sum their values, record sum / count as the level's average, and enqueue their children.
Capturing the queue size before dequeuing is what separates the levels. Every node enqueued during a round is a child of a current-level node, so it belongs to the next level, and the loop bound guarantees none of those children are processed until the following round. No markers or sentinel values are needed.
Algorithm
- Initialize a queue and add the root to it. (The constraints guarantee at least one node.)
- 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).
A 64-bit accumulator is the simplest answer to overflow, but a running mean avoids large intermediates entirely: for the k-th value v dequeued at a level, update avg += (v - avg) / k. The intermediate values stay within the range of the node values, at the cost of slightly different floating-point rounding along the way.
BFS visits each node once, so its time is optimal. Its memory cost is the queue, which peaks at the widest level. The same per-level sums and counts can be collected during a depth-first traversal, where the memory cost is the recursion stack instead of a queue.
Approach 2: DFS (Depth-First Search)
Intuition
DFS does not process nodes level by level, but every recursive call knows its depth. Passing the current depth as a parameter lets us accumulate the sum and count for each level in two parallel lists indexed by depth. After the traversal finishes, sums[i] / counts[i] is the average for level i.
BFS groups nodes by level through the queue. DFS reaches the same grouping by using depth as an index into the tracking lists. Only the visit order differs.
The memory trade-off depends on the tree's shape. For a balanced tree, the recursion stack holds O(log n) frames while the BFS queue peaks at O(n) nodes on the widest level, so DFS uses far less memory. For a skewed tree the comparison flips: the stack grows to O(n) while the BFS queue never holds more than a node or two.
The result does not depend on visit order. Each node contributes its value once to sums[depth] and once to counts[depth], and addition is commutative, so any traversal that visits every node exactly once produces the same two lists. Whether node 9 is visited before or after node 20 is irrelevant; both contribute to level 1.
The depth == sums.size() check detects the first visit to each depth. A node at depth d is reached only through its parent at depth d - 1, which was visited first, so depth never exceeds sums.size() at the moment a node is visited. The lists grow one level at a time, with no gaps.
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 and do O(1) work per node (add to sum, increment count). The final pass to compute averages is one division per level, at most O(n).
- Space Complexity: O(h) where h is the height of the tree, for the recursion call stack (O(n) worst case for a skewed tree; O(log n) for a balanced tree). The sums and counts lists hold one entry per level, which is O(h) as well.
The recursion can also be replaced with an explicit stack of (node, depth) pairs. The bookkeeping is identical, and it removes the risk of stack overflow on a deep, skewed tree.