What is the brute force approach and complexity for Average of Levels in Binary Tree?

Walk the whole tree once for each depth, adding up the nodes at that depth with time complexity O(N · H) and space complexity O(H).

What is the optimal approach and complexity for Average of Levels in Binary Tree?

Pop one whole level per round from a queue; the round's size tells you how many nodes to pop with optimal time complexity O(N) and space complexity O(W).

How do you identify the pattern for Average of Levels in Binary Tree?

Look for key signals in the prompt: "average of the values on each level" indicates One number per level, so the answer is grouped by depth, not by path or by subtree.; "each level" indicates A level is the set of nodes that share a depth. That is exactly one BFS round.; "from top to bottom" indicates Rounds run from the top down, so the order of the rounds is the order of the answer. No sorting is needed..

Average of Levels in Binary Tree

Easy·LeetCode #637Basic Anchor

LeetCode

Jump:

30-Second Mental ModelTree BFS (level by level) — per-round aggregate

Complexity:O(N · H)→O(N)

Key Insight

Use a queue, as in level-order traversal. At the start of each round the queue holds exactly one whole level. Remember how many nodes it holds, pop exactly that many while adding their values, and push their children behind them. Then divide the round's sum by that count.

Core Validity Invariant

A round is correct when it pops exactly the size nodes that were in the queue at its start, and nothing else. The children it pushes wait behind them for the next round.

Problem

You are given the root of a binary tree.

For each level of the tree, find the average of the node values on that level. Return one average per level, from the top level (the root) down to the bottom level.

A level is all the nodes that are the same distance from the root. Answers within 10^-5 of the exact average are accepted.

Input

The root of a binary tree. The tree is never empty.

Output

An array of decimal numbers: the average of each level, top to bottom.

Example 1

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

Output: [3.0, 14.5, 11.0]

Level 0 is just 3, so its average is 3. Level 1 has 9 and 20: (9 + 20) / 2 = 14.5. Level 2 has 15 and 7: (15 + 7) / 2 = 11.

Example 2

Input: root = [3, 9, 20, 15, 7]

Output: [3.0, 14.5, 11.0]

This tree has 15 and 7 as the children of 9 instead of 20. The level averages are still 3, 14.5 and 11.

Constraints

• The number of nodes is between 1 and 10^4.
• −2^31 ≤ Node.val ≤ 2^31 − 1
• Answers within 10^-5 of the exact average are accepted.

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
Is one round of the algorithm one node, or all the nodes that share a depth?
2.
Which traversal hands me the nodes of one level together: depth-first or breadth-first?
3.
Should I divide by the number of nodes on this level, or by the number of nodes in the whole tree?
4.
Node values can be as large as 2^31 − 1. What happens if two of them are added in a 32-bit int?
5.
If I do not know how deep the tree is, how will I know when to stop?

Brute force approach

Idea

Pick a depth d. Every walk starts again at the root and visits the whole tree. Add up the values of the nodes whose depth is d, and count them. Divide the sum by the count. Repeat for d = 0, 1, 2, … until a depth has no nodes.

Thinking process

1
The average of a level needs two things: the sum of its nodes and how many nodes it has. A depth-first walk can tell each node its depth if we pass the depth down the recursion.
2
For depth 0 we walk the whole tree and only count the root. On [3, 9, 20, null, null, 15, 7] that is just 3, so the average is 3.
3
For depth 1 we walk the whole tree again. Only 9 and 20 match, so the sum is 29, the count is 2, and the average is 14.5.
4
Depth 2 needs another full walk: 15 and 7 match, the sum is 22, the count is 2, and the average is 11. A walk for depth 3 finds nothing, so we stop.
5
Each walk visits all 5 nodes, and there are 4 walks. No walk reuses anything from the one before it.

Visual

Each walk starts again at the root and visits every node. Blue = the node being visited now, green = a node added to this depth's sum, grey = a node walked over because it is at another depth. The same nodes are visited again for every depth.

Depth by depthroot = [3, 9, 20, null, null, 15, 7]step 1/28

Walk

depth looked for: 0
nodes at this depth: 0
sum so far: 0
whole-tree visits: 0

Averages so far

[ ]

Walk 1: look for depth 0, starting again at the root

Depth 0 needs a fresh walk of the whole tree (5 nodes). Nothing from the earlier walks is reused.

Code & Implementation

brute.cpp

class Solution {
    // Adds up the nodes at depth `target`. Walks the whole tree from `node`.
    void sumDepth(TreeNode* node, int depth, int target, long long& sum, long long& count) {
        if (!node) return;
        if (depth == target) {
            sum += node->val;
            count++;
        }
        sumDepth(node->left, depth + 1, target, sum, count);
        sumDepth(node->right, depth + 1, target, sum, count);
    }

public:
    vector<double> averageOfLevels(TreeNode* root) {
        vector<double> res;
        // One full walk of the tree per depth. Stop at the first depth with no nodes.
        for (int d = 0;; d++) {
            long long sum = 0, count = 0;
            sumDepth(root, 0, d, sum, count);
            if (count == 0) break;
            res.push_back((double)sum / count);
        }
        return res;
    }
};

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    // Adds up the nodes at depth `target`. Walks the whole tree from `node`.
    private void sumDepth(TreeNode node, int depth, int target, long[] acc) {
        if (node == null) return;
        if (depth == target) {
            acc[0] += node.val;
            acc[1]++;
        }
        sumDepth(node.left, depth + 1, target, acc);
        sumDepth(node.right, depth + 1, target, acc);
    }

    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> res = new ArrayList<>();
        // One full walk of the tree per depth. Stop at the first depth with no nodes.
        for (int d = 0;; d++) {
            long[] acc = new long[2]; // acc[0] = sum, acc[1] = count
            sumDepth(root, 0, d, acc);
            if (acc[1] == 0) break;
            res.add((double) acc[0] / acc[1]);
        }
        return res;
    }
}

from typing import Optional, List
from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
        # Adds up the nodes at depth `target`. Walks the whole tree from `node`.
        def sum_depth(node: Optional[TreeNode], depth: int, target: int, acc: List[int]) -> None:
            if not node:
                return
            if depth == target:
                acc[0] += node.val
                acc[1] += 1
            sum_depth(node.left, depth + 1, target, acc)
            sum_depth(node.right, depth + 1, target, acc)

        res: List[float] = []
        # One full walk of the tree per depth. Stop at the first depth with no nodes.
        d = 0
        while True:
            acc = [0, 0]  # [sum, count]
            sum_depth(root, 0, d, acc)
            if acc[1] == 0:
                break
            res.append(acc[0] / acc[1])
            d += 1
        return res

export class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = (val === undefined ? 0 : val);
        this.left = (left === undefined ? null : left);
        this.right = (right === undefined ? null : right);
    }
}

// Adds up the nodes at depth `target`. Walks the whole tree from `node`.
function sumDepth(node: TreeNode | null, depth: number, target: number, acc: [number, number]): void {
    if (!node) return;
    if (depth === target) {
        acc[0] += node.val;
        acc[1]++;
    }
    sumDepth(node.left, depth + 1, target, acc);
    sumDepth(node.right, depth + 1, target, acc);
}

export function averageOfLevels(root: TreeNode | null): number[] {
    const res: number[] = [];
    // One full walk of the tree per depth. Stop at the first depth with no nodes.
    for (let d = 0;; d++) {
        const acc: [number, number] = [0, 0];
        sumDepth(root, 0, d, acc);
        if (acc[1] === 0) break;
        res.push(acc[0] / acc[1]);
    }
    return res;
}

Complexity

Time O(N · H)Space O(H)

N is the number of nodes and H is the height. Every walk visits all N nodes, and there are H + 1 walks plus one empty check. The optimal version reads each node exactly once, so it is O(N) for the same answer. What it saves is the repeated walks over the same nodes.

Optimized approach

Idea

Start from brute force

Brute force walks the whole tree once for every depth. Each walk adds up the nodes of that one depth and ignores everything else.

Find the repeated work

Every walk visits every node again, so each node is read once for every depth that exists, even though it belongs to exactly one level. Level-order traversal reads each node once and gathers each level's nodes at the same time.

Define the state — what variables do I need?

queue: Nodes waiting to be popped. At the start of a round it holds exactly one whole level.
size: How many nodes are in the queue when the round starts. Those nodes are this round's level.
sum: Total of the values popped in this round. It is a `long long`, so it cannot overflow.

Define validity

A round is correct when it pops exactly the size nodes that were in the queue at its start, and nothing else. The children it pushes wait behind them for the next round.

Define the transitions — when does each pointer move, and why is it safe?

Start of a round

size = queue.size(); sum = 0

The queue holds exactly one level right now, so size is that level's node count. Children pushed later in the round do not change size.

Each pop in the round

sum += node->val; push node->left and node->right if they exist

The children are one level lower, so they go to the back of the queue and wait for the next round.

End of a round

res.push_back((double)sum / size)

All of the level's nodes have been added, so the average is complete. The cast makes the division a decimal division.

What does the current window add to the answer?

Each round finishes one whole level and produces one average, so the answer has one entry per level, top to bottom.

Code & Implementation

optimal.cpp

class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        vector<double> res;
        if (!root) return res;

        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            int size = q.size();      // nodes in this round = this whole level
            long long sum = 0;        // a level can add up past 2^31, so use 64 bits
            for (int i = 0; i < size; i++) {
                TreeNode* node = q.front();
                q.pop();
                sum += node->val;
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            // Cast first: sum / size on two integers would cut 14.5 down to 14.
            res.push_back((double)sum / size);
        }
        return res;
    }
};

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> res = new ArrayList<>();
        if (root == null) return res;

        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            int size = q.size();      // nodes in this round = this whole level
            long sum = 0;             // a level can add up past 2^31, so use 64 bits
            for (int i = 0; i < size; i++) {
                TreeNode node = q.poll();
                sum += node.val;
                if (node.left != null) q.offer(node.left);
                if (node.right != null) q.offer(node.right);
            }
            // Cast first: sum / size on two integers would cut 14.5 down to 14.
            res.add((double) sum / size);
        }
        return res;
    }
}

from typing import Optional, List
from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
        res: List[float] = []
        if not root:
            return res

        q: deque[TreeNode] = deque([root])
        while q:
            size = len(q)      # nodes in this round = this whole level
            sum_val = 0        # a level can add up past 2^31, so use 64 bits
            for _ in range(size):
                node = q.popleft()
                sum_val += node.val
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            # Cast first: sum / size on two integers would cut 14.5 down to 14.
            res.append(sum_val / size)
        return res

export class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = (val === undefined ? 0 : val);
        this.left = (left === undefined ? null : left);
        this.right = (right === undefined ? null : right);
    }
}

export function averageOfLevels(root: TreeNode | null): number[] {
    const res: number[] = [];
    if (!root) return res;

    const q: TreeNode[] = [root];
    while (q.length > 0) {
        const size = q.length;      // nodes in this round = this whole level
        let sum = 0;                // a level can add up past 2^31, so use 64 bits
        for (let i = 0; i < size; i++) {
            const node = q.shift()!;
            sum += node.val;
            if (node.left) q.push(node.left);
            if (node.right) q.push(node.right);
        }
        // Cast first: sum / size on two integers would cut 14.5 down to 14.
        res.push(sum / size);
    }
    return res;
}

Complexity

Time O(N)Space O(W)

Each node is pushed once and popped once, so the time is O(N). The queue holds nodes from at most two levels at a time, so the space is O(W), where W is the widest level's node count. The brute force above repeats the walk once per depth, so it is O(N · H).

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Walk the whole tree once for each depth, adding up the nodes at that depth	O(N · H)	O(H)
Optimal	Pop one whole level per round from a queue; the round's size tells you how many nodes to pop	O(N)	O(W)

Why does this belong to this pattern?

Clues in the problem statement

“average of the values on each level”One number per level, so the answer is grouped by depth, not by path or by subtree.
“each level”A level is the set of nodes that share a depth. That is exactly one BFS round.
“from top to bottom”Rounds run from the top down, so the order of the rounds is the order of the answer. No sorting is needed.

Group nodes by depth+one BFS round per level+aggregate: sum ÷ round size→Tree BFS (level by level) — per-round aggregate

This is the anchor for the sub-pattern: one BFS round is exactly one level, so any per-level number is the round's total divided by the round's size. The new part compared with plain level order is the divisor: it is this round's size, not the size of the whole tree. Also, the sum needs 64 bits, because each node value can be as large as 2^31 − 1.

Don't make this mistake

Summing a level into an int

✗ int sum = 0;

✓ long long sum = 0;

Two nodes of value 2^31 − 1 already overflow a 32-bit int. On [2147483647, 2147483647, 2147483647] the second level's int sum wraps around to −2, so its average comes out as −1 instead of 2147483647.

Dividing with integers

✗ res.push_back(sum / size);

✓ res.push_back((double)sum / size);

On [3, 9, 20, null, null, 15, 7] the second level has sum 29 and size 2. Integer division gives 14, but the answer is 14.5.

Confusing it with the average of the whole tree

✗ res.push_back((double)sum / totalNodes);

✓ res.push_back((double)sum / size);

Each answer is about one level. On [3, 9, 20, null, null, 15, 7] there are 5 nodes in total, so the second level would become 29 / 5 = 5.8 instead of 14.5. The divisor is the number of nodes in this round.

Forgetting to reset the sum each round

✗ long long sum = 0; // declared once, above the while loop

✓ long long sum = 0; // declared inside the round, so it starts at 0 each time

The second level would also add the root's 3, so the answer becomes (3 + 9 + 20) / 2 = 16 instead of 14.5. Each round must start from zero.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Tree BFS translate into production architectures and low-level memory mechanics.

LLD Architecture