Loading…

easyTreesLC #637Sometimes asked

Average of Levels in Binary Tree

Q: How do you solve Average of Levels in Binary Tree using the DFS Carrying Depth with Per-Level (sum, count) approach?

When to use it: Offer as an alternative when asked for a recursive solution, or to show you can group by level without a queue. BFS makes levels explicit through the queue, but DFS can group by level too if we carry the current depth as a parameter and tally into arrays indexed by depth. **Why pass the depth.** In DFS we descend along paths rather than rows, so a node's level isn't implicit in the traversal order. Threading `depth` through each recursive call tells every node which bucket it belongs to. The root is depth 0, its children depth 1, and so on. **Why two parallel arrays.** To compute an average we need both the total and the count for each level. `sums[d]` accumulates the values at depth `d`, and `counts[d]` accumulates how many nodes contributed. When we visit a node at depth `d`, we add its value to `sums[d]` and increment `counts[d]`. If `d` is a depth we've never reached, we extend the arrays first. As with BFS, the sum bucket should be a `long`/`double` to avoid overflow. **Why the result comes out ordered.** Because depth `d` indexes directly into the arrays, level 0's tallies live at index 0, level 1's at index 1, and so on. After the DFS completes we walk the arrays from index 0 upward, dividing `sums[d] / counts[d]`, and the averages emerge already in top-to-bottom order — no sorting needed. **Why this trades space differently than BFS.** DFS uses `O(h)` recursion stack instead of `O(w)` queue width, which can be a win on wide, shallow trees and a loss on deep, skinny ones. The per-level arrays add `O(L)` where `L` is the number of levels. Functionally identical result; the choice between BFS and DFS here is really a choice about which dimension (width vs height) you'd rather pay for. Time complexity: O(n). Space complexity: O(h).

LCPractice

Trees & BST · 14 of 41 · 8 min

Given the root of a binary tree, return the average value of the nodes on each level in the form of an array.

Answers within 10⁻⁵ of the actual answer will be accepted.

In plain English

We must compute one number — the mean of all node values — for each level of the tree, and return them ordered from the root's level downward. The defining challenge is grouping nodes by depth, which BFS does naturally if we process the queue one level at a time. The value range reaching ±2³¹ is a deliberate hint that summing a level can overflow a 32-bit integer.

Examples

Example 1

Input: root = [3,9,20,null,null,15,7]
Output: [3.00000, 14.50000, 11.00000]
Note: Level 0 = [3] → 3. Level 1 = [9, 20] → 14.5. Level 2 = [15, 7] → 11.

Example 2

Input: root = [3,9,20,15,7]
Output: [3.00000, 14.50000, 11.00000]
Note: Same averages: level 1 is [9,20] and level 2 is [15,7].

Example 3

Input: root = [2147483647]
Output: [2147483647.00000]
Note: A single Integer.MAX_VALUE node — its own average. Two such on one level would overflow an int sum, motivating a long accumulator.

Constraints

The number of nodes is in the range [1, 10⁴]
-2³¹ ≤ Node.val ≤ 2³¹ − 1
The answer is an array of doubles, one per level, top to bottom

Clarifying questions4First question: How big can node values get, and does that affect the sum?Explore questions

Q1.How big can node values get, and does that affect the sum?
They span the full 32-bit range (±2³¹). A single level of many near-max values overflows int, so the running sum must be a long (or a double).
Q2.What order should the averages appear in?
Top to bottom — the root's level first, then each successive level. BFS produces exactly this order.
Q3.Can the tree be empty?
The constraint says at least 1 node, but a robust solution returns an empty list for a null root.
Q4.BFS or DFS?
BFS is the natural fit because levels are the unit of work. DFS works too if you carry the depth and accumulate (sum, count) per level into parallel arrays.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

This is level-order traversal with one extra step. Run BFS, but process the queue one full level at a time: snapshot the queue's size before the inner loop, sum exactly that many nodes' values, divide by the count, and append the average. The size-snapshot is the trick that draws a clean boundary between levels. Use a long (or double) accumulator — node values can be near the int limit and a level of them overflows int.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can run a level-aware BFS by snapshotting the queue size to delimit levels, and whether you anticipate integer overflow when summing many large values per level.

Where candidates slip

Reading queue.size() inside the loop (so it changes as children are added, mixing levels), or summing into an int and overflowing on a wide level of near-max values.

How to stand out

Name the size-snapshot idiom explicitly, mention the overflow guard (long/double accumulator) before being asked, and note the DFS alternative that carries depth and tallies (sum, count) per level.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Level-Order BFS with a Frozen Queue Size (Optimal)Optimal	`O(n)`	`O(w)`	Lead with this — it's the natural and expected answer. Frame it as 'BFS, but reduce one level at a time by snapshotting the queue size'.	Read
2	DFS Carrying Depth with Per-Level (sum, count)	`O(n)`	`O(h)`	Offer as an alternative when asked for a recursive solution, or to show you can group by level without a queue.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewqueue = [root]queue empty?YesNoExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2 · Optimal

Level-Order BFS with a Frozen Queue Size (Optimal)

TimeO(n)SpaceO(w)

Lead with this — it's the natural and expected answer. Frame it as 'BFS, but reduce one level at a time by snapshotting the queue size'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Averages are per LEVEL, and BFS visits nodes level by level. How do you know where one level ends and the next begins inside the queue?

2Hint 2Explore hint

At the top of each outer iteration, the queue holds exactly one full level. Record its size first, then loop that many times, summing values and enqueuing children.

3Hint 3Explore hint

Divide the level's sum by the count you recorded. Watch the accumulator type — many large values can overflow a 32-bit int, so sum into a long or double.

A · Core idea

Breadth-first traversal already visits nodes level by level; the only addition this problem needs is a way to know exactly where each level ends so we can reduce it independently. The elegant solution is to snapshot the queue's size at the start of each outer iteration.

Why the size snapshot delimits levels. At the moment we enter the outer while, the queue contains precisely the nodes of the current level and nothing else — we haven't enqueued any of their children yet. So size = queue.length captures that level's width. We then loop exactly size times, and during those iterations we append children to the back of the queue. Because we only iterate size times, those freshly-added children are untouched this round — they form the next level, to be processed on the following outer iteration. If instead we read queue.length live inside the loop, it would grow as children are added and we'd merge multiple levels into one sum.

Why the accumulator must be wider than int. The constraint allows node values up to 2³¹ − 1 (Integer.MAX_VALUE). A level can contain many such values, and even two of them sum to more than a 32-bit signed int can hold, wrapping around to a negative number. So in Java we accumulate into a long (or a double); in Python integers are arbitrary precision so the sum is safe, but we still divide as a float. This overflow guard is exactly the kind of detail interviewers probe — stating it unprompted signals real care.

Why we divide by the recorded count, not a constant. Levels widen as you descend (until the last, possibly-partial level), so each level has its own node count. We divide that level's sum by the size we snapshotted, producing the mean. Storing the count up front, before the queue mutates, keeps the division correct.

Why only non-null children get enqueued. We push a child only if it exists. Enqueuing nulls would inflate the next level's size, throwing off both the iteration count and the divisor, and would crash when we later read .val off a null. Skipping nulls keeps size equal to the true number of real nodes on the level.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

root = [3,9,20,null,null,15,7]

Interactive diagram

Levels of [3,9,20,null,null,15,7]

level 0

Active call / nodeSupporting contextReturned stateNot active

Each dashed group is one BFS level; the average is computed over the nodes in that group.

Final result[3.00000, 14.50000, 11.00000]

C · Code with teaching comments

solution.javaJava

Level-Order BFS with a Frozen Queue Size (Optimal) — optimal

5 teaching notes

1
// Definition for a binary tree node.
2
class TreeNode {
3
    int val;
4
    TreeNode left;
5
    TreeNode right;
6
    TreeNode(int val) { this.val = val; }
7
}
8
 
9
public List<Double> averageOfLevels(TreeNode root) {
10
    List<Double> result = new ArrayList<>();
11
    if (root == null) return result;
12
    Queue<TreeNode> queue = new LinkedList<>();
13
    queue.offer(root);
14
    while (!queue.isEmpty()) {
15
        int size = queue.size();          // freeze this level's width
16
        long sum = 0;                      // long guards against int overflow
17
        // Iterate exactly size times so next level's children (added below) aren't
18
        // counted this round.
19
        for (int i = 0; i < size; i++) {
20
            TreeNode node = queue.poll();
21
            sum += node.val;
22
            // Enqueue only real children; nulls would inflate the next size and crash
23
            // on .val.
24
            if (node.left != null) queue.offer(node.left);
25
            if (node.right != null) queue.offer(node.right);
26
        }
27
        result.add((double) sum / size);   // average of this level
28
    }
29
    return result;
30
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.30 lines

D · Why it works and complexityO(n) timeO(w) spaceOpen the invariant and proofExplore the proof

The whole template is 'freeze the width, then drain exactly that many'. That single line — size = queue.length before the inner loop — converts a flat BFS into a level-aware one, and it's the shared backbone of Level Order Traversal, Right Side View, Zigzag, and this problem. Change only the per-level reduction (here: sum then divide).

ComplexityO(n) time, O(w) space — Each node is enqueued and dequeued exactly once with O(1) work → O(n) time. The queue holds at most one level at a time, so its peak size is the maximum level width w → O(w) space, which is O(n) for a wide bottom level.

E · Edge cases and pitfalls7root = [1] — One level: size=1, sum=1 → [1.0].Explore edge cases

Edge cases handled

root = [1]One level: size=1, sum=1 → [1.0].
root = [2147483647,2147483647,2147483647]Level 1 sums two Integer.MAX_VALUE — overflows int but fits in long → correct average.
Left-skewed treeEach level has exactly one node; queue width stays 1, averages equal the node values down the spine.

Pitfalls

Reading queue.size() inside the inner loop, merging levels as children are added.
Summing into an int and overflowing on wide levels of large values.
Enqueuing null children, inflating the divisor and crashing on .val.
Forgetting to cast before dividing in Java, yielding integer division.

03.2

Approach 2 of 2

DFS Carrying Depth with Per-Level (sum, count)

TimeO(n)SpaceO(h)

Offer as an alternative when asked for a recursive solution, or to show you can group by level without a queue.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Without a queue, how do you know which level a node belongs to during a DFS? Pass the depth down.

2Hint 2Explore hint

Maintain two parallel arrays indexed by depth: one accumulating the sum of values at that depth, one counting nodes at that depth.

3Hint 3Explore hint

After the traversal, divide each level's sum by its count to get the averages, already in top-to-bottom order.

A · Core idea

BFS makes levels explicit through the queue, but DFS can group by level too if we carry the current depth as a parameter and tally into arrays indexed by depth.

Why pass the depth. In DFS we descend along paths rather than rows, so a node's level isn't implicit in the traversal order. Threading depth through each recursive call tells every node which bucket it belongs to. The root is depth 0, its children depth 1, and so on.

Why two parallel arrays. To compute an average we need both the total and the count for each level. sums[d] accumulates the values at depth d, and counts[d] accumulates how many nodes contributed. When we visit a node at depth d, we add its value to sums[d] and increment counts[d]. If d is a depth we've never reached, we extend the arrays first. As with BFS, the sum bucket should be a long/double to avoid overflow.

Why the result comes out ordered. Because depth d indexes directly into the arrays, level 0's tallies live at index 0, level 1's at index 1, and so on. After the DFS completes we walk the arrays from index 0 upward, dividing sums[d] / counts[d], and the averages emerge already in top-to-bottom order — no sorting needed.

Why this trades space differently than BFS. DFS uses O(h) recursion stack instead of O(w) queue width, which can be a win on wide, shallow trees and a loss on deep, skinny ones. The per-level arrays add O(L) where L is the number of levels. Functionally identical result; the choice between BFS and DFS here is really a choice about which dimension (width vs height) you'd rather pay for.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

root = [3,9,20,null,null,15,7]

visit 3 @d0

sums=[3], counts=[1]

Statedepth 0 started

Final result[3.00000, 14.50000, 11.00000]

C · Code with teaching comments

Reference implementation previewpublic List<Double> averageOfLevels(TreeNode root) { List<Long> sums = new ArrayList<>(); List<Integer> counts = new ArrayList<>(); dfs(root, 0, sums, counts); List<Double> result = new ArrayList<>();Explore the full code

solution.javaJava

DFS Carrying Depth with Per-Level (sum, count) — reference

4 teaching notes

1
public List<Double> averageOfLevels(TreeNode root) {
2
    List<Long> sums = new ArrayList<>();
3
    List<Integer> counts = new ArrayList<>();
4
    // Start at depth 0; sums/counts grow as new depths are reached.
5
    dfs(root, 0, sums, counts);
6
    List<Double> result = new ArrayList<>();
7
    for (int d = 0; d < sums.size(); d++) {
8
        result.add((double) sums.get(d) / counts.get(d));
9
    }
10
    return result;
11
}
12
 
13
private void dfs(TreeNode node, int depth, List<Long> sums, List<Integer> counts) {
14
    if (node == null) return;
15
    if (depth == sums.size()) {            // first node seen at this depth
16
        sums.add(0L);
17
        counts.add(0);
18
    }
19
    // Accumulate the value into this level's long sum, avoiding int overflow.
20
    sums.set(depth, sums.get(depth) + node.val);
21
    counts.set(depth, counts.get(depth) + 1);
22
    // Descend with depth+1 so children land in the next level's bucket.
23
    dfs(node.left, depth + 1, sums, counts);
24
    dfs(node.right, depth + 1, sums, counts);
25
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.25 lines

D · Why it works and complexityO(n) timeO(h) spaceOpen the invariant and proofExplore the proof

Indexing tallies by depth turns DFS into a level-grouping tool. Recognizing that 'a quantity per level' can be computed by either freezing the BFS queue or by depth-indexed accumulation in DFS is a transferable insight — pick whichever traversal's space profile suits the tree shape.

ComplexityO(n) time, O(h) space — Each node is visited once and updates its depth's tallies in O(1) → O(n) time. Recursion depth is the tree height h → O(h) stack space, plus O(L) for the per-level arrays where L is the number of levels (≤ n).

E · Edge cases and pitfalls7root = [1] — sums=[1], counts=[1] → [1.0].Explore edge cases

Edge cases handled

root = [1]sums=[1], counts=[1] → [1.0].
Deep right-skewed treeDFS recursion depth O(n); each level has one node so averages equal the spine values.
Negative and positive values mixingLong sum handles cancellation correctly; average can be negative.

Pitfalls

Using int for the per-level sum array, reintroducing overflow.
Forgetting to extend the arrays when a new depth is first reached.
Passing the same depth to both children instead of depth+1.
Dividing with integer division instead of producing a float.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code preview// Definition for a binary tree node. class TreeNode { int val; TreeNode left; TreeNode right;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Live queue size inside the loop

If the inner loop bound re-reads queue.size() each iteration, it grows as children are enqueued, so you keep dequeuing into the same 'level' and merge multiple levels into one average.

Explore the code comparison

Don't write this

while (!queue.isEmpty()) {
    long sum = 0;
    for (int i = 0; i < queue.size(); i++) {   // size changes as we enqueue!
        TreeNode node = queue.poll();
        sum += node.val;
        if (node.left != null) queue.offer(node.left);
        if (node.right != null) queue.offer(node.right);
    }
}

Write this instead

while (!queue.isEmpty()) {
    int size = queue.size();   // freeze first
    long sum = 0;
    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);
    }
}

Integer overflow on the level sum

Node values reach Integer.MAX_VALUE. Summing several into an int wraps around to a negative number, producing a wildly wrong average.

Explore the code comparison

Don't write this

int sum = 0;                     // overflows on big values
for (int i = 0; i < size; i++) {
    sum += queue.poll().val;
}
result.add((double) sum / size);

Write this instead

long sum = 0;                    // wide enough to hold a level of max values
for (int i = 0; i < size; i++) {
    sum += queue.poll().val;
}
result.add((double) sum / size);

Integer division of the average

Dividing two ints in Java truncates toward zero, so 29/2 becomes 14 instead of 14.5. Cast the numerator (or use a double) before dividing.

Explore the code comparison

Don't write this

result.add((double) (sum / size));   // division happens in int first → 14.0

Write this instead

result.add((double) sum / size);     // cast first → true 14.5

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Level-by-level BFS with a per-level sum and count

Code pattern to memorize

queue = [root]
while queue not empty:
    size = len(queue)            # freeze this level's width
    levelSum = 0
    for i in range(size):        # exactly one level
        node = queue.pop_front()
        levelSum += node.val
        enqueue node's children
    result.append(levelSum / size)

Rules to remember

1Snapshot size = queue.length before the inner loop — it freezes the current level's width as children get enqueued.
2Iterate exactly size times so the next level's nodes don't bleed into this level's sum.
3Accumulate into a long (Java) or float (Python) — a level of int values can overflow a 32-bit int.
4Divide by the node count of that level, not by anything fixed — levels have different widths.
5Enqueue non-null children only; never push nulls or you'll divide by an inflated count.

Use this pattern when

You need a per-level aggregate (average, sum, max, min, count)
Processing must respect level boundaries — node depth matters
Breadth-first order is natural; you want results top-to-bottom by level
Any 'for each row of the tree, compute X' phrasing

Choose another pattern when

Order within a level must alternate → still BFS, but Zigzag Level Order
You only need the last value of each level → Right Side View (take the last per level)
The aggregate is over root-to-leaf paths, not levels → DFS instead
Depth doesn't matter, just a global aggregate → a plain DFS sum is simpler

Interview takeaway

Average of Levels is the cleanest demonstration of the 'freeze the queue size' BFS template. Once you internalize snapshotting size before the inner loop, the entire family of level-order problems — sums, maxima, right-side view, zigzag — becomes the same loop with a different per-level reduction.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternLevel-aware BFS via the frozen-queue-size idiom. Recognise it whenever you need a per-level aggregate or per-level grouping. Swap the reduction (sum/average, max, last element, full list) and the same loop solves Level Order Traversal, Right Side View, Largest Value in Each Row, and Zigzag.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Binary Tree Level Order Traversal
Same level-freeze BFS, but collect the values into a list per level instead of averaging.
Binary Tree Right Side View
Take the last node of each level during the same BFS.
Binary Tree Zigzag Level Order Traversal
Level-order BFS, but reverse alternate levels with a direction flag.
Find Largest Value in Each Tree Row
Coming soon
Identical loop, but take the max of each level instead of the average.

Same pattern

←

Binary Tree Maximum Path Sum

Continue · Next problem

Binary Tree Zigzag Level Order Traversal

easyTreesLC #637Sometimes asked

Average of Levels in Binary Tree

LCPractice

Trees & BST · 14 of 41 · 8 min

Given the root of a binary tree, return the average value of the nodes on each level in the form of an array.

Answers within 10⁻⁵ of the actual answer will be accepted.

In plain English

Examples

Example 1

Input: root = [3,9,20,null,null,15,7]
Output: [3.00000, 14.50000, 11.00000]
Note: Level 0 = [3] → 3. Level 1 = [9, 20] → 14.5. Level 2 = [15, 7] → 11.

Example 2

Input: root = [3,9,20,15,7]
Output: [3.00000, 14.50000, 11.00000]
Note: Same averages: level 1 is [9,20] and level 2 is [15,7].

Example 3

Input: root = [2147483647]
Output: [2147483647.00000]
Note: A single Integer.MAX_VALUE node — its own average. Two such on one level would overflow an int sum, motivating a long accumulator.

Constraints

The number of nodes is in the range [1, 10⁴]
-2³¹ ≤ Node.val ≤ 2³¹ − 1
The answer is an array of doubles, one per level, top to bottom

Clarifying questions4First question: How big can node values get, and does that affect the sum?Explore questions

Q1.How big can node values get, and does that affect the sum?
They span the full 32-bit range (±2³¹). A single level of many near-max values overflows int, so the running sum must be a long (or a double).
Q2.What order should the averages appear in?
Top to bottom — the root's level first, then each successive level. BFS produces exactly this order.
Q3.Can the tree be empty?
The constraint says at least 1 node, but a robust solution returns an empty list for a null root.
Q4.BFS or DFS?
BFS is the natural fit because levels are the unit of work. DFS works too if you carry the depth and accumulate (sum, count) per level into parallel arrays.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can run a level-aware BFS by snapshotting the queue size to delimit levels, and whether you anticipate integer overflow when summing many large values per level.

Where candidates slip

Reading queue.size() inside the loop (so it changes as children are added, mixing levels), or summing into an int and overflowing on a wide level of near-max values.

How to stand out

Name the size-snapshot idiom explicitly, mention the overflow guard (long/double accumulator) before being asked, and note the DFS alternative that carries depth and tallies (sum, count) per level.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Level-Order BFS with a Frozen Queue Size (Optimal)Optimal	`O(n)`	`O(w)`	Lead with this — it's the natural and expected answer. Frame it as 'BFS, but reduce one level at a time by snapshotting the queue size'.	Read
2	DFS Carrying Depth with Per-Level (sum, count)	`O(n)`	`O(h)`	Offer as an alternative when asked for a recursive solution, or to show you can group by level without a queue.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2 · Optimal

Level-Order BFS with a Frozen Queue Size (Optimal)

TimeO(n)SpaceO(w)

Lead with this — it's the natural and expected answer. Frame it as 'BFS, but reduce one level at a time by snapshotting the queue size'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Averages are per LEVEL, and BFS visits nodes level by level. How do you know where one level ends and the next begins inside the queue?

2Hint 2Explore hint

At the top of each outer iteration, the queue holds exactly one full level. Record its size first, then loop that many times, summing values and enqueuing children.

3Hint 3Explore hint

Divide the level's sum by the count you recorded. Watch the accumulator type — many large values can overflow a 32-bit int, so sum into a long or double.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

root = [3,9,20,null,null,15,7]

Interactive diagram

Levels of [3,9,20,null,null,15,7]

level 0

Active call / nodeSupporting contextReturned stateNot active

Each dashed group is one BFS level; the average is computed over the nodes in that group.

Final result[3.00000, 14.50000, 11.00000]

C · Code with teaching comments

solution.javaJava

Level-Order BFS with a Frozen Queue Size (Optimal) — optimal

5 teaching notes

1
// Definition for a binary tree node.
2
class TreeNode {
3
    int val;
4
    TreeNode left;
5
    TreeNode right;
6
    TreeNode(int val) { this.val = val; }
7
}
8
 
9
public List<Double> averageOfLevels(TreeNode root) {
10
    List<Double> result = new ArrayList<>();
11
    if (root == null) return result;
12
    Queue<TreeNode> queue = new LinkedList<>();
13
    queue.offer(root);
14
    while (!queue.isEmpty()) {
15
        int size = queue.size();          // freeze this level's width
16
        long sum = 0;                      // long guards against int overflow
17
        // Iterate exactly size times so next level's children (added below) aren't
18
        // counted this round.
19
        for (int i = 0; i < size; i++) {
20
            TreeNode node = queue.poll();
21
            sum += node.val;
22
            // Enqueue only real children; nulls would inflate the next size and crash
23
            // on .val.
24
            if (node.left != null) queue.offer(node.left);
25
            if (node.right != null) queue.offer(node.right);
26
        }
27
        result.add((double) sum / size);   // average of this level
28
    }
29
    return result;
30
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.30 lines

D · Why it works and complexityO(n) timeO(w) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls7root = [1] — One level: size=1, sum=1 → [1.0].Explore edge cases

Edge cases handled

root = [1]One level: size=1, sum=1 → [1.0].
root = [2147483647,2147483647,2147483647]Level 1 sums two Integer.MAX_VALUE — overflows int but fits in long → correct average.
Left-skewed treeEach level has exactly one node; queue width stays 1, averages equal the node values down the spine.

Pitfalls

Reading queue.size() inside the inner loop, merging levels as children are added.
Summing into an int and overflowing on wide levels of large values.
Enqueuing null children, inflating the divisor and crashing on .val.
Forgetting to cast before dividing in Java, yielding integer division.

03.2

Approach 2 of 2

DFS Carrying Depth with Per-Level (sum, count)

TimeO(n)SpaceO(h)

Offer as an alternative when asked for a recursive solution, or to show you can group by level without a queue.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Without a queue, how do you know which level a node belongs to during a DFS? Pass the depth down.

2Hint 2Explore hint

Maintain two parallel arrays indexed by depth: one accumulating the sum of values at that depth, one counting nodes at that depth.

3Hint 3Explore hint

After the traversal, divide each level's sum by its count to get the averages, already in top-to-bottom order.

A · Core idea

BFS makes levels explicit through the queue, but DFS can group by level too if we carry the current depth as a parameter and tally into arrays indexed by depth.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

root = [3,9,20,null,null,15,7]

visit 3 @d0

sums=[3], counts=[1]

Statedepth 0 started

Final result[3.00000, 14.50000, 11.00000]

C · Code with teaching comments

solution.javaJava

DFS Carrying Depth with Per-Level (sum, count) — reference

4 teaching notes

1
public List<Double> averageOfLevels(TreeNode root) {
2
    List<Long> sums = new ArrayList<>();
3
    List<Integer> counts = new ArrayList<>();
4
    // Start at depth 0; sums/counts grow as new depths are reached.
5
    dfs(root, 0, sums, counts);
6
    List<Double> result = new ArrayList<>();
7
    for (int d = 0; d < sums.size(); d++) {
8
        result.add((double) sums.get(d) / counts.get(d));
9
    }
10
    return result;
11
}
12
 
13
private void dfs(TreeNode node, int depth, List<Long> sums, List<Integer> counts) {
14
    if (node == null) return;
15
    if (depth == sums.size()) {            // first node seen at this depth
16
        sums.add(0L);
17
        counts.add(0);
18
    }
19
    // Accumulate the value into this level's long sum, avoiding int overflow.
20
    sums.set(depth, sums.get(depth) + node.val);
21
    counts.set(depth, counts.get(depth) + 1);
22
    // Descend with depth+1 so children land in the next level's bucket.
23
    dfs(node.left, depth + 1, sums, counts);
24
    dfs(node.right, depth + 1, sums, counts);
25
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.25 lines

D · Why it works and complexityO(n) timeO(h) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls7root = [1] — sums=[1], counts=[1] → [1.0].Explore edge cases

Edge cases handled

root = [1]sums=[1], counts=[1] → [1.0].
Deep right-skewed treeDFS recursion depth O(n); each level has one node so averages equal the spine values.
Negative and positive values mixingLong sum handles cancellation correctly; average can be negative.

Pitfalls

Using int for the per-level sum array, reintroducing overflow.
Forgetting to extend the arrays when a new depth is first reached.
Passing the same depth to both children instead of depth+1.
Dividing with integer division instead of producing a float.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code preview// Definition for a binary tree node. class TreeNode { int val; TreeNode left; TreeNode right;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Live queue size inside the loop

If the inner loop bound re-reads queue.size() each iteration, it grows as children are enqueued, so you keep dequeuing into the same 'level' and merge multiple levels into one average.

Explore the code comparison

Don't write this

while (!queue.isEmpty()) {
    long sum = 0;
    for (int i = 0; i < queue.size(); i++) {   // size changes as we enqueue!
        TreeNode node = queue.poll();
        sum += node.val;
        if (node.left != null) queue.offer(node.left);
        if (node.right != null) queue.offer(node.right);
    }
}

Write this instead

while (!queue.isEmpty()) {
    int size = queue.size();   // freeze first
    long sum = 0;
    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);
    }
}

Integer overflow on the level sum

Node values reach Integer.MAX_VALUE. Summing several into an int wraps around to a negative number, producing a wildly wrong average.

Explore the code comparison

Don't write this

int sum = 0;                     // overflows on big values
for (int i = 0; i < size; i++) {
    sum += queue.poll().val;
}
result.add((double) sum / size);

Write this instead

long sum = 0;                    // wide enough to hold a level of max values
for (int i = 0; i < size; i++) {
    sum += queue.poll().val;
}
result.add((double) sum / size);

Integer division of the average

Dividing two ints in Java truncates toward zero, so 29/2 becomes 14 instead of 14.5. Cast the numerator (or use a double) before dividing.

Explore the code comparison

Don't write this

result.add((double) (sum / size));   // division happens in int first → 14.0

Write this instead

result.add((double) sum / size);     // cast first → true 14.5

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Level-by-level BFS with a per-level sum and count

Code pattern to memorize

queue = [root]
while queue not empty:
    size = len(queue)            # freeze this level's width
    levelSum = 0
    for i in range(size):        # exactly one level
        node = queue.pop_front()
        levelSum += node.val
        enqueue node's children
    result.append(levelSum / size)

Rules to remember

1Snapshot size = queue.length before the inner loop — it freezes the current level's width as children get enqueued.
2Iterate exactly size times so the next level's nodes don't bleed into this level's sum.
3Accumulate into a long (Java) or float (Python) — a level of int values can overflow a 32-bit int.
4Divide by the node count of that level, not by anything fixed — levels have different widths.
5Enqueue non-null children only; never push nulls or you'll divide by an inflated count.

Use this pattern when

You need a per-level aggregate (average, sum, max, min, count)
Processing must respect level boundaries — node depth matters
Breadth-first order is natural; you want results top-to-bottom by level
Any 'for each row of the tree, compute X' phrasing

Choose another pattern when

Order within a level must alternate → still BFS, but Zigzag Level Order
You only need the last value of each level → Right Side View (take the last per level)
The aggregate is over root-to-leaf paths, not levels → DFS instead
Depth doesn't matter, just a global aggregate → a plain DFS sum is simpler

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Binary Tree Level Order Traversal
Same level-freeze BFS, but collect the values into a list per level instead of averaging.
Binary Tree Right Side View
Take the last node of each level during the same BFS.
Binary Tree Zigzag Level Order Traversal
Level-order BFS, but reverse alternate levels with a direction flag.
Find Largest Value in Each Tree Row
Coming soon
Identical loop, but take the max of each level instead of the average.

Same pattern

←

Binary Tree Maximum Path Sum

Continue · Next problem

Binary Tree Zigzag Level Order Traversal