DSA sheet · Trees · BFS (level order) pattern

Average of Levels in Binary Tree

Third problem in the level order pattern. Instead of printing each level, we report one number per level: the average of its values. The teacher uses it to teach two habits: don't store what you don't need (keep a running sum instead of a list of values), and read the value range so the sum doesn't overflow. She solves it with BFS (brute force, then optimised), then shows why DFS can't average "on the spot" and fixes that with two small arrays.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting
• Part A · Brute force BFS: store every level, then average
• Part B · Optimal BFS: a running sum per level
• Part C · DFS with a sum array and a count array
• Part D · Revision page

Part 0 · Before starting

The tree node

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

Words we need

• Level: a row of the tree. The root is level 0, its children level 1, and so on. A child's level is its parent's level + 1.
• Average of a level = (sum of the values on that level) ÷ (how many nodes are on that level).
• Level order traversal (the prerequisite video): BFS with a queue, where size = len(queue) at the start of each round tells us how many nodes make up the current level. The teacher says if you don't know that yet, watch it first, because this problem is a small edit of it.

from collections import deque

class Solution:
    def levelOrder(self, root):
        ans = []
        if root is None:
            return ans
        queue = deque([root])
        while queue:
            size = len(queue)          # nodes on the current level
            level = []
            for i in range(size):
                node = queue.popleft()
                level.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            ans.append(level)
        return ans

Part A · Brute force BFS

LeetCode 637 · Average of Levels in Binary Tree

1The question in simple words

Given the root of a binary tree, return a list with the average value of the nodes on each level, from top to bottom. Answers within 10⁻⁵ of the true value are accepted.

        3          level 0: 3 ÷ 1        = 3.0
       / \
      9   20       level 1: (9+20) ÷ 2   = 14.5
         /  \
        15   7     level 2: (15+7) ÷ 2   = 11.0

Answer: [3.0, 14.5, 11.0].

2What the constraints tell us

• Number of nodes: 1 to 10⁴ → at least one node, so the root is never None. With BFS we don't need the "if root is None" check. (In DFS we still need a base case, because it's what stops the recursion.)
• n up to 10⁴ → an O(n²) idea would be 10⁸ steps, which is too slow (the teacher's limit: around 10⁸ operations gets risky). So we must stay at O(n).
• Values: −2³¹ to 2³¹ − 1. That's the full range of a 32-bit int. If a value is already at the maximum and we add even one more number, the sum goes past the limit and overflows (in Java/C++). So the sum must be kept in a long (or a double).

3Intuition

Level order traversal already gives us the rows: [[3], [9, 20], [15, 7]]. Once we have a row, its average is just "add them up, divide by how many". So the first plan is: get all the rows, then average each row.

4Building the logic from the example

1. Run plain level order → [[3], [9, 20], [15, 7]].
2. Row [3]: sum 3, count 1 → 3.0.
3. Row [9, 20]: sum 29, count 2 → 14.5.
4. Row [15, 7]: sum 22, count 2 → 11.0.

Why it's only brute force

• Filling the rows costs O(n) time and O(n) extra space to hold every value.
• Then another O(n) pass to sum all the rows. Total about O(2n), still linear.
• The real waste is the space. The teacher's question: when we pop 3, or 9, why not add it to a sum right there instead of putting it in a list first? We only ever need the sum and the count, not the values. That's Part B.

5Approach steps

1. Put the root in a queue (no empty check, the constraints promise a root).
2. Do plain level order and collect each level as a list.
3. For each stored level, append sum(level) / len(level) to the answer.
4. Return the answer.

6Code (Python)

from collections import deque

class Solution:
    def averageOfLevels(self, root):
        levels = []
        queue = deque([root])               # constraints: root always exists
        while queue:
            size = len(queue)
            level = []
            for i in range(size):
                node = queue.popleft()
                level.append(node.val)      # store the value (the waste)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            levels.append(level)
        ans = []
        for level in levels:                # second pass
            ans.append(sum(level) / len(level))
        return ans

7Code line by line

8Dry run

1. BFS gives levels = [[3], [9, 20], [15, 7]] (same queue steps as plain level order).
2. Second pass: 3/1 = 3.0 → 29/2 = 14.5 → 22/2 = 11.0.
3. Return [3.0, 14.5, 11.0].

9Complexity & remember

• Time O(n) + O(n) = O(2n) = O(n).
• Space O(n) for the queue, plus O(n) for storing all values in levels.

Part B · Optimal BFS: running sum

1The question, and 2 the constraints

Same as Part A: at least 1 node (no empty check in BFS), up to 10⁴ nodes (O(n) needed), and full-int values (sum in a long / float in other languages).

3Intuition: replace the row list with a number

For the average we only need two numbers per level: the sum and the count. The count is already there for free: it's size, the number of nodes in this level. So swap the row list for a single total variable, and add each value to it the moment we pop the node.

4Building the logic: edit the level order code line by line

The teacher literally starts from the level order code and changes it:

5Approach steps

1. Put the root in the queue.
2. While the queue isn't empty: size = len(queue), total = 0.
3. Pop size nodes; add each value to total; push its children.
4. After the for loop, append total / size.
5. Return the list of averages.

6Code (Python)

from collections import deque

class Solution:
    def averageOfLevels(self, root):
        ans = []
        queue = deque([root])               # constraints: at least 1 node
        while queue:
            size = len(queue)
            total = 0                       # fresh sum for this level
            for i in range(size):
                node = queue.popleft()
                total += node.val           # add instead of storing
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            ans.append(total / size)        # average of this level
        return ans

7Code line by line

8Dry run on the example

9Complexity & remember

• Time O(n): every node is pushed once and popped once.
• Space O(n) worst case, for the queue. The teacher shows why with a full tree of 7 nodes: queue [1] → pop 1, push 2, 3 → pop 2, push 4, 5 → queue [3, 4, 5] → pop 3, push 6, 7 → queue [4, 5, 6, 7]. The biggest the queue gets is the last level, about n/2 nodes, which is O(n).
• What we saved: the extra O(n) list of all values from Part A. The level's data is now O(1): one sum.

         1
       /   \
      2     3
     / \   / \
    4   5 6   7     ← queue holds these 4 at once (≈ n/2)

Part C · DFS with sum and count arrays

1The question

Same question, now with recursion. The teacher shows the idea and the code and asks you to try it yourself. For this part she uses a tree with more nodes on level 2:

         3            level 0
       /   \
      9     20        level 1
     / \   /  \
    4   6 15   7      level 2

Expected: level 0 → 3/1 = 3.0, level 1 → 29/2 = 14.5, level 2 → (4+6+15+7)/4 = 32/4 = 8.0. Answer [3.0, 14.5, 8.0].

2What the constraints tell us

• Recursion → always write the base case if root is None: return, even though the root itself exists. The children of leaves are None, and that's where the recursion has to stop.
• Same overflow note: the per-level sums should be long in Java/C++.

3Intuition: why DFS can't average on the spot

In BFS, all nodes of a level come out together, one after the other. So when the for loop ends, the level is complete and we can divide right away.

DFS goes deep first. On this tree it visits 3 → 9 → 4 → 6 → 20 → 15 → 7. When it's at 9, it doesn't know about 20 yet, which is on the same level. Level 2's nodes arrive at four different moments. We can't divide until the whole traversal is over, so we must remember something per level.

The teacher gives two options:

1. Do a full level order traversal with DFS (store every value per level), then average each row. That's the Part A waste again.
2. Better: keep two small arrays, indexed by level: sums[level] and counts[level]. Each node adds its value to its level's sum and adds 1 to its level's count. At the end, divide them.

4Building the logic

• Pass the level into each call: the root gets 0, children get level + 1. The call stack remembers each call's level.
• The index of the arrays is the level: sums[2] is "the sum of everything on level 2".
• We don't know the number of levels in advance, so we grow the arrays: when level == len(sums), this is the first node we've seen on that level → append a 0 to both arrays.
• At a node: sums[level] += val and counts[level] += 1.
• After the DFS: ans[i] = sums[i] / counts[i] for each level i.

5Approach steps

1. Make empty sums and counts; call dfs(root, 0).
2. In dfs: if the node is None, return.
3. If level == len(sums), append 0 to both arrays.
4. Add the value to sums[level], add 1 to counts[level].
5. Recurse left with level + 1, then right with level + 1.
6. After the DFS, loop over the levels and append sums[i] / counts[i].

6Code (Python)

class Solution:
    def averageOfLevels(self, root):
        sums, counts = [], []
        self.dfs(root, 0, sums, counts)
        ans = []
        for i in range(len(sums)):          # one pass over the levels
            ans.append(sums[i] / counts[i])
        return ans

    def dfs(self, root, level, sums, counts):
        if root is None:                    # base case: stops the recursion
            return
        if level == len(sums):              # first node on this level
            sums.append(0)
            counts.append(0)
        sums[level] += root.val
        counts[level] += 1
        self.dfs(root.left, level + 1, sums, counts)
        self.dfs(root.right, level + 1, sums, counts)

7Code line by line

8Dry run: watch the two arrays

Final pass: 3/1 = 3.0, 29/2 = 14.5, 32/4 = 8.0 → [3.0, 14.5, 8.0].

9Complexity & remember

• Time O(n) for the DFS, plus one loop over the levels (O(height)) to divide.
• Extra space O(height): two arrays with one slot per level, plus the call stack, which is also as tall as the tree.

Part D · Revision page

t1 = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
t2 = TreeNode(3, TreeNode(9, TreeNode(4), TreeNode(6)), TreeNode(20, TreeNode(15), TreeNode(7)))
big = TreeNode(2147483647, TreeNode(2147483647), TreeNode(2147483647))

s = Solution()
print(s.averageOfLevels(t1))     # [3.0, 14.5, 11.0]
print(s.averageOfLevels(t2))     # [3.0, 14.5, 8.0]
print(s.averageOfLevels(big))    # [2147483647.0, 2147483647.0]

Based on this video: Average of Levels in Binary Tree | BFS & DFS