Skip to main content
Talentd

Average of Levels in Binary Tree - Solution & Explanation

EasyTreeDepth-First SearchBreadth-First SearchBinary Tree27 min readAsked at: Amazon, Microsoft, Meta +1
Practice this problem

Problem Statement

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-5 of the actual answer will be accepted.

 

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: [3.00000,14.50000,11.00000]
Explanation: The average value of nodes on level 0 is 3, on level 1 is 14.5, and on level 2 is 11.
Hence return [3, 14.5, 11].

Example 2:

Input: root = [3,9,20,15,7]
Output: [3.00000,14.50000,11.00000]

 

Constraints:

  • The number of nodes in the tree is in the range [1, 104].
  • -231 <= Node.val <= 231 - 1

Approach Overview

Problem Overview: You are given the root of a binary tree and need to compute the average value of nodes at every depth level. The result should return one average per level, starting from the root and moving downward.

Approach 1: Breadth-First Search (BFS) Using Queue (Time: O(n), Space: O(w))

This approach performs a level-order traversal using a queue. Push the root into the queue, then repeatedly process nodes level by level. For each level, track the number of nodes currently in the queue, iterate through them, accumulate their values, and push their children into the queue. After processing the level, compute the average as levelSum / levelSize and append it to the result list. BFS naturally groups nodes by depth, making it the most straightforward way to compute per-level aggregates in a breadth-first search traversal.

This method visits every node exactly once, giving O(n) time complexity where n is the number of nodes in the tree. Space complexity is O(w), where w is the maximum width of the tree (the largest number of nodes at any level). For balanced trees, this can approach O(n). In practice, BFS is usually the clearest and most interview-friendly solution for problems that require level-based processing.

Approach 2: Depth-First Search (DFS) With Pre-order Traversal (Time: O(n), Space: O(h))

The DFS solution uses recursion to traverse the tree while tracking the current depth. Maintain two arrays (or lists): one storing the cumulative sum of values per level and another storing the count of nodes per level. During a depth-first search, whenever you visit a node, check whether the current depth already exists in the arrays. If not, initialize it. Then update the sum and increment the node count for that level.

After the traversal completes, compute each level's average by dividing the stored sum by the count. The traversal itself still touches every node once, resulting in O(n) time complexity. Space complexity is O(h) for the recursion stack, where h is the height of the tree, plus the arrays that store level sums and counts. DFS works well when recursion feels more natural or when you want tighter control over traversal logic in a binary tree.

Recommended for interviews: The BFS queue solution is typically what interviewers expect first because the problem explicitly asks for level-based results. It maps directly to level-order traversal and keeps the implementation simple. Showing the DFS variant demonstrates deeper understanding of tree traversal patterns and how to aggregate values across recursion levels.

Approach 1: Breadth-First Search (BFS) Using Queue

This approach uses a Breadth-First Search (BFS) strategy to traverse the binary tree level by level. For each level, we calculate the sum of node values and the count of nodes, then compute the average for each level. The BFS technique helps in handling each level independently using a queue.

In this C solution, we implement the BFS traversal using a queue. We enqueue the root node first, then for each node, enqueue its children. The sum and count for each level are calculated, and averages are printed. This method ensures that each level is fully processed before the next begins.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(N), where N is the number of nodes in the tree, as each node is processed once.
Space Complexity: O(M), where M is the maximum number of nodes at any level, corresponding to the queue holding these nodes.

Try this approach in the editor →

Approach 2: Depth-First Search (DFS) With Pre-order Traversal

This approach makes use of Depth-First Search (DFS) combined with pre-order traversal. The key idea is to traverse the tree, keeping track of the sum of node values and the count of nodes at each level. Recursive traversal helps gather the necessary values efficiently for averaging.

This C solution employs a depth-first approach that recursively calculates level sums and counts. The dfs function updates these for each node, with results computed for levels in the end.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(N), where N signifies the number of tree nodes.
Space Complexity: O(H), where H is the height of the tree due to recursion stack.

Try this approach in the editor →

Approach 3: BFS

We can use the Breadth-First Search (BFS) method to traverse the nodes of each level and calculate the average value of each level.

Specifically, we define a queue q, initially adding the root node to the queue. Each time, we take out all the nodes in the queue, calculate their average value, add it to the answer array, and then add their child nodes to the queue. Repeat this process until the queue is empty.

The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree.

Code

PythonJavaC++GoRustJavaScript

Python

Java

C++

Go

Rust

JavaScript

Try this approach in the editor →

Approach 4: DFS

We can also use the Depth-First Search (DFS) method to calculate the average value of each level.

Specifically, we define an array s, where s[i] is a tuple representing the sum of node values and the number of nodes at the i-th level. We perform a depth-first search on the tree. For each node, we add the node's value to the corresponding s[i] and increment the node count by one. Finally, for each s[i], we calculate the average value and add it to the answer array.

The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree.

Code

PythonJavaC++GoJavaScript

Python

Java

C++

Go

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Breadth-First Search (BFS) Using Queue

Time Complexity: O(N), where N is the number of nodes in the tree, as each node is processed once.
Space Complexity: O(M), where M is the maximum number of nodes at any level, corresponding to the queue holding these nodes.

Depth-First Search (DFS) With Pre-order Traversal

Time Complexity: O(N), where N signifies the number of tree nodes.
Space Complexity: O(H), where H is the height of the tree due to recursion stack.

BFS—
DFS—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Breadth-First Search (BFS) Using QueueO(n)O(w)Best when computing values level-by-level in a tree; most intuitive approach
Depth-First Search (DFS) With Pre-order TraversalO(n)O(h)Useful when recursion is preferred or when aggregating results per depth

Video Solution

LeetCode 637. Average of Levels in Binary Tree (Algorithm Explained) • Nick White • 14,589 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Average of Levels in Binary Tree easy or hard?
Average of Levels in Binary Tree is categorized as an Easy problem. The logic relies on basic tree traversal, particularly level-order traversal with BFS. Once you understand how to process nodes level by level, implementing the average calculation is straightforward.
Average of Levels in Binary Tree Python/Java solution
In Python or Java, the typical implementation uses a queue for BFS. For each level, iterate through the nodes currently in the queue, accumulate their values, and enqueue their children. After processing the level, divide the total by the number of nodes to compute the average.
How to solve Average of Levels in Binary Tree in O(n)?
Traverse the tree once and compute level-wise sums. Using BFS, process nodes level by level with a queue, sum their values, and divide by the number of nodes in that level. Alternatively, use DFS with recursion while storing cumulative sums and counts per depth. Both strategies achieve O(n) time complexity.
What is the best approach for Average of Levels in Binary Tree?
Breadth-First Search (BFS) using a queue is the most direct solution. Level-order traversal naturally processes nodes level by level, allowing you to compute the sum and count of nodes for each level in one pass. The approach runs in O(n) time and uses O(w) space where w is the maximum width of the tree.
Is Average of Levels in Binary Tree asked at Google/Amazon/Meta?
Binary tree traversal problems like this frequently appear in interviews at companies such as Amazon, Google, Meta, and Microsoft. Variations often test level-order traversal, aggregation per level, or tree-based statistics. Interviewers use them to evaluate understanding of BFS and DFS patterns.
What data structure is used in Average of Levels in Binary Tree?
The primary data structure is a queue when using the BFS approach to perform level-order traversal. For the DFS approach, recursion is used along with arrays or lists that store the cumulative sum and node count for each depth level.
What is the time complexity of Average of Levels in Binary Tree?
The time complexity is O(n) because each node in the binary tree is visited exactly once. Both BFS and DFS solutions perform a single traversal of the tree. The difference lies mainly in space usage depending on the traversal method.

Ready to solve this problem?

Practice Average of Levels in Binary Tree with our built-in code editor and test cases.

Practice on FleetCode
Previous

Binary Tree Level Order Traversal

Next

Binary Tree Level Order Traversal II