LeetCode 637 - Average of Levels in Binary Tree

Difficulty: 🟢 Easy
Topics: Tree, Depth-First Search, Breadth-First Search, Binary Tree

Solution

Problem Understanding

In this problem, we are given the root node of a binary tree, and we need to compute the average value of all nodes at each depth level of the tree.

A binary tree is organized into levels. The root node is at level 0, its children are at level 1, their children are at level 2, and so on. For every level, we must calculate:

The sum of all node values on that level
The number of nodes on that level
The average, which is sum / count

The result should be returned as an array of floating point numbers, where the element at index i represents the average value of all nodes at level i.

For example, consider this tree:

The levels are:

Level 0: [3], average = 3
Level 1: [9, 20], average = (9 + 20) / 2 = 14.5
Level 2: [15, 7], average = (15 + 7) / 2 = 11

So the output becomes:

[3.0, 14.5, 11.0]

The constraints tell us that the tree can contain up to 10^4 nodes. This means the solution must be efficient enough to process every node only a small number of times. Since every node contributes to exactly one level average, an O(n) solution is ideal.

The node values may also be very large, including negative values. This means we should avoid assumptions such as all sums being positive.

Several edge cases are important:

A tree with only one node
A completely skewed tree, where every node has only one child
Trees containing negative values
Large trees with many levels
Levels containing very large sums

The problem guarantees that the tree contains at least one node, so we never receive an empty tree.

Approaches

Brute Force Approach

A brute force solution would first determine the height of the tree, then for every level separately, traverse the entire tree again to collect all nodes belonging to that level.

For example:

Compute tree height
For level 0, traverse the whole tree and collect nodes at depth 0
For level 1, traverse the whole tree again
Continue until the deepest level

This works because every traversal correctly identifies the nodes belonging to a specific depth. However, it is inefficient because the same nodes are revisited many times.

If the tree has n nodes and height h, the complexity becomes O(n * h). In the worst case, a skewed tree has height n, leading to O(n^2) time complexity.

This is unnecessarily expensive because we can process all levels in a single traversal.

Optimal Approach

The key observation is that binary trees are naturally suited for level order traversal using Breadth-First Search, BFS.

BFS processes nodes level by level:

Start with the root
Process all nodes currently in the queue
Add their children to the queue
Move to the next level

Because the queue already groups nodes by traversal level, we can compute:

The total sum of the current level
The number of nodes on the current level

Then we directly calculate the average before moving to the next level.

Each node is visited exactly once, making this approach linear in time complexity.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n * h)	O(h)	Re-traverses the tree separately for every level
Optimal	O(n)	O(w)	Uses BFS to process each node exactly once

Here:

n is the number of nodes
h is the tree height
w is the maximum width of the tree

Algorithm Walkthrough

BFS Level Order Traversal

Create an empty result array to store averages for each level.
Initialize a queue with the root node. A queue is ideal because BFS requires first-in-first-out processing.
While the queue is not empty, process one level at a time.
Determine the number of nodes currently in the queue. This count represents all nodes belonging to the current level.
Initialize a variable to store the sum of values for the current level.
Process exactly level_size nodes:

Remove a node from the front of the queue
Add its value to the current level sum
If the node has a left child, add it to the queue
If the node has a right child, add it to the queue

After processing the entire level, compute:

average = level_sum / level_size

Append the computed average to the result array.
Continue until all levels are processed.
Return the result array.

Why it works

The queue always contains nodes grouped by traversal order. At the beginning of each iteration, the queue holds exactly the nodes for one tree level. By processing exactly level_size nodes before moving forward, we guarantee that the computed sum and count belong only to that level. Since every node is visited exactly once and contributes to exactly one level sum, all averages are computed correctly.

Python Solution

from collections import deque
from typing import List, Optional

# Definition for a binary tree node.
# 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]:
        result = []
        queue = deque([root])

        while queue:
            level_size = len(queue)
            level_sum = 0

            for _ in range(level_size):
                node = queue.popleft()
                level_sum += node.val

                if node.left:
                    queue.append(node.left)

                if node.right:
                    queue.append(node.right)

            result.append(level_sum / level_size)

        return result

The implementation begins by creating a queue initialized with the root node. The queue enables level order traversal, which is the natural way to process tree levels independently.

Inside the main loop, level_size captures how many nodes belong to the current level. This is important because new child nodes added during processing belong to the next level and should not affect the current average.

The inner loop processes every node at the current level. Each node contributes its value to level_sum, and its children are added to the queue for future processing.

After all nodes at the current level are processed, the average is computed and appended to the result list.

Finally, once the queue becomes empty, all levels have been processed and the result is returned.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func averageOfLevels(root *TreeNode) []float64 {
    result := []float64{}
    queue := []*TreeNode{root}

    for len(queue) > 0 {
        levelSize := len(queue)
        levelSum := 0

        for i := 0; i < levelSize; i++ {
            node := queue[0]
            queue = queue[1:]

            levelSum += node.Val

            if node.Left != nil {
                queue = append(queue, node.Left)
            }

            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }

        average := float64(levelSum) / float64(levelSize)
        result = append(result, average)
    }

    return result
}

The Go implementation follows the same BFS strategy as the Python solution.

Instead of Python's deque, Go uses a slice to simulate a queue. Nodes are removed from the front using:

queue = queue[1:]

Because integer division in Go truncates decimals, both the sum and size are converted to float64 before division.

Go also uses explicit nil checks for child nodes before appending them to the queue.

Worked Examples

Example 1

Input:

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

Tree:

Initial State

Variable	Value
queue	[3]
result	[]

Level 0

Step	Action	Queue After Action	Level Sum
1	Remove 3	[]	3
2	Add children 9 and 20	[9, 20]	3

Average:

3 / 1 = 3.0

Result:

[3.0]

Level 1

Step	Action	Queue After Action	Level Sum
1	Remove 9	[20]	9
2	Remove 20	[]	29
3	Add children 15 and 7	[15, 7]	29

Average:

29 / 2 = 14.5

Result:

[3.0, 14.5]

Level 2

Step	Action	Queue After Action	Level Sum
1	Remove 15	[7]	15
2	Remove 7	[]	22

Average:

22 / 2 = 11.0

Final result:

[3.0, 14.5, 11.0]

Example 2

Input:

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

Tree:

Level Processing

Level	Nodes	Sum	Count	Average
0	[3]	3	1	3.0
1	[9, 20]	29	2	14.5
2	[15, 7]	22	2	11.0

Final output:

[3.0, 14.5, 11.0]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Every node is visited exactly once
Space	O(w)	Queue stores at most one tree level at a time

The algorithm performs a standard BFS traversal. Since every node enters and leaves the queue exactly once, the total work is linear in the number of nodes.

The space complexity depends on the maximum number of nodes present at any single level of the tree. In the worst case, a complete binary tree may contain approximately n / 2 nodes on the last level, giving O(w) auxiliary space.

Test Cases

from collections import deque
from typing import Optional, List

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]:
        result = []
        queue = deque([root])

        while queue:
            level_size = len(queue)
            level_sum = 0

            for _ in range(level_size):
                node = queue.popleft()
                level_sum += node.val

                if node.left:
                    queue.append(node.left)

                if node.right:
                    queue.append(node.right)

            result.append(level_sum / level_size)

        return result

solution = Solution()

# Example 1
root1 = TreeNode(3)
root1.left = TreeNode(9)
root1.right = TreeNode(20)
root1.right.left = TreeNode(15)
root1.right.right = TreeNode(7)

assert solution.averageOfLevels(root1) == [3.0, 14.5, 11.0]  # standard balanced tree

# Example 2
root2 = TreeNode(3)
root2.left = TreeNode(9, TreeNode(15), TreeNode(7))
root2.right = TreeNode(20)

assert solution.averageOfLevels(root2) == [3.0, 14.5, 11.0]  # different structure, same averages

# Single node tree
root3 = TreeNode(5)

assert solution.averageOfLevels(root3) == [5.0]  # minimum valid tree

# Left skewed tree
root4 = TreeNode(1)
root4.left = TreeNode(2)
root4.left.left = TreeNode(3)
root4.left.left.left = TreeNode(4)

assert solution.averageOfLevels(root4) == [1.0, 2.0, 3.0, 4.0]  # one node per level

# Tree with negative values
root5 = TreeNode(-10)
root5.left = TreeNode(-20)
root5.right = TreeNode(-30)

assert solution.averageOfLevels(root5) == [-10.0, -25.0]  # negative averages

# Mixed positive and negative values
root6 = TreeNode(5)
root6.left = TreeNode(-5)
root6.right = TreeNode(15)

assert solution.averageOfLevels(root6) == [5.0, 5.0]  # average with mixed signs

# Complete binary tree
root7 = TreeNode(1)
root7.left = TreeNode(2)
root7.right = TreeNode(3)
root7.left.left = TreeNode(4)
root7.left.right = TreeNode(5)
root7.right.left = TreeNode(6)
root7.right.right = TreeNode(7)

assert solution.averageOfLevels(root7) == [1.0, 2.5, 5.5]  # full tree

print("All test cases passed.")

Test	Why
Balanced tree example	Verifies standard BFS level processing
Alternate structure example	Confirms averages depend on levels, not shape
Single node tree	Tests minimum input size
Left skewed tree	Tests deep tree with width 1
Negative values	Ensures averages handle negatives correctly
Mixed positive and negative values	Verifies arithmetic correctness
Complete binary tree	Tests wide levels and queue growth

Edge Cases

Single Node Tree

A tree containing only the root node is the smallest valid input. This case is important because some implementations accidentally assume the existence of child nodes or multiple levels.

For example:

The correct result is:

[5.0]

The implementation handles this naturally because the queue initially contains only the root. The BFS loop processes one level and terminates cleanly.

Skewed Tree

A skewed tree behaves similarly to a linked list:

In this situation, every level contains exactly one node. Some incorrect implementations may assume multiple nodes per level or mishandle queue updates.

The BFS solution works correctly because level_size becomes 1 for every iteration, producing one average per level.

Negative Node Values

The problem allows negative integers:

      -10
      / \
   -20  -30

The average of the second level becomes:

(-20 + -30) / 2 = -25

Some implementations incorrectly initialize sums or assume non-negative values. The presented solution simply performs normal arithmetic, so negative numbers are handled without any special logic.

Very Wide Levels

Complete binary trees can contain many nodes on a single level. This tests whether the queue correctly manages large batches of nodes.

Because the algorithm processes nodes level by level and stores only the current frontier, it efficiently handles large widths while maintaining linear time complexity.