Average of Levels in Binary Tree solution and explanation
Google
9 more videos on this problem
LeetCode 637. Average of Levels in Binary Tree (Algorithm Explained)Nick White · 6:25 · 14K views
Average of Levels Binary Tree (LeetCode 637) | Solution with easy explanation | Study AlgorithmsNikhil Lohia · 11:46 · 7K views
Average of Levels in Binary Tree - Leetcode 637 - Trees (Python)Greg Hogg · 3:48 · 6K views
Average of Levels in Binary Tree | Live Coding with Explanation | Leetcode - 637Algorithms Made Easy · 6:51 · 3K views
[Python] - Leetcode 637 - Average of Levels in Binary Tree in O(N) ComplexityBrevity - Code Intuitively · 7:55 · 908 views
637. Average of Levels in Binary Tree | Leetcode | PythonAbdullah Arshed · 6:02 · 421 views
637. Average of Levels in Binary Tree - English VersionSimple Code - 단순코드 · 4:22 · 357 views
Average of Levels in Binary Tree | C++ | Leetcode Solution 637Gantavya Malviya · 9:57 · 329 views
LeetCode 637. Average of Levels in Binary Tree | JSer - JavaScript & AlgorithmJSer · 2:45 · 231 views
Daily Leetcode #885: Sep 02, 2022 - 637. Average of Levels in Binary TreeProgramming Live with Larry · 5:09 · 230 views
The problem
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.
from collections import deque
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def averageOfLevels(self, root):
if not root:
return []
averages = []
queue = deque([root])
while queue:
level_sum, level_count = 0, len(queue)
for _ in range(level_count):
node = queue.popleft()
level_sum += node.val
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
averages.append(level_sum / level_count)
return averages
# Example Usage
if __name__ == "__main__":
a = TreeNode(3)
b = TreeNode(9)
c = TreeNode(20)
d = TreeNode(15)
e = TreeNode(7)
a.left = b
a.right = c
c.left = d
c.right = e
solution = Solution()
result = solution.averageOfLevels(a)
print(result)import java.util.*;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Solution {
public List<Double> averageOfLevels(TreeNode root) {
List<Double> averages = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int count = queue.size();
double sum = 0;
for (int i = 0; i < count; i++) {
TreeNode node = queue.poll();
sum += node.val;
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
averages.add(sum / count);
}
return averages;
}
public static void main(String[] args) {
TreeNode a = new TreeNode(3);
TreeNode b = new TreeNode(9);
TreeNode c = new TreeNode(20);
TreeNode d = new TreeNode(15);
TreeNode e = new TreeNode(7);
a.left = b;
a.right = c;
c.left = d;
c.right = e;
Solution sol = new Solution();
List<Double> result = sol.averageOfLevels(a);
result.forEach(avg -> System.out.print(avg + " "));
}
}#include <iostream>
#include <queue>
#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
vector<double> averageOfLevels(TreeNode* root) {
vector<double> averages;
if (!root) return averages;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
long sum = 0, count = 0;
queue<TreeNode*> temp;
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
sum += node->val;
count++;
if (node->left) temp.push(node->left);
if (node->right) temp.push(node->right);
}
averages.push_back((double)sum / count);
swap(q, temp);
}
return averages;
}
int main() {
/* Create Binary tree with nodes */
TreeNode a(3), b(9), c(20), d(15), e(7);
a.left = &b;
a.right = &c;
c.left = &d;
c.right = &e;
vector<double> result = averageOfLevels(&a);
for (double avg : result) {
cout << avg << " ";
}
return 0;
}class TreeNode {
constructor(val, left = null, right = null) {
this.val = val;
this.left = left;
this.right = right;
}
}
function averageOfLevels(root) {
const averages = [];
const queue = [root];
while (queue.length > 0) {
const count = queue.length;
let sum = 0;
for (let i = 0; i < count; i++) {
const node = queue.shift();
sum += node.val;
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
averages.push(sum / count);
}
return averages;
}
// Example usage
const a = new TreeNode(3);
const b = new TreeNode(9);
const c = new TreeNode(20);
const d = new TreeNode(15);
const e = new TreeNode(7);
a.left = b;
a.right = c;
c.left = d;
c.right = e;
console.log(averageOfLevels(a));#include <stdio.h>
#include <stdlib.h>
#include <math.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
struct QueueNode {
struct TreeNode *node;
struct QueueNode *next;
};
struct Queue {
struct QueueNode *front, *rear;
};
struct Queue* createQueue() {
struct Queue* q = (struct Queue*)malloc(sizeof(struct Queue));
q->front = q->rear = NULL;
return q;
}
void enqueue(struct Queue* q, struct TreeNode* node) {
struct QueueNode* newNode = (struct QueueNode*)malloc(sizeof(struct QueueNode));
newNode->node = node;
newNode->next = NULL;
if (q->rear == NULL) {
q->front = q->rear = newNode;
return;
}
q->rear->next = newNode;
q->rear = newNode;
}
struct TreeNode* dequeue(struct Queue* q) {
if (q->front == NULL) return NULL;
struct QueueNode* temp = q->front;
q->front = q->front->next;
if (q->front == NULL) q->rear = NULL;
struct TreeNode* node = temp->node;
free(temp);
return node;
}
int isQueueEmpty(struct Queue* q) {
return q->front == NULL;
}
// Function to find average of nodes at each level
void averageOfLevels(struct TreeNode* root) {
if (!root) return;
struct Queue* q = createQueue();
enqueue(q, root);
while (!isQueueEmpty(q)) {
int count = 0;
double sum = 0;
struct Queue* level = createQueue();
while (!isQueueEmpty(q)) {
struct TreeNode* node = dequeue(q);
sum += node->val;
count++;
if (node->left) enqueue(level, node->left);
if (node->right) enqueue(level, node->right);
}
printf("%.5f ", sum / count);
free(q);
q = level;
}
}
int main() {
/* Create Binary tree with nodes */
struct TreeNode a, b, c, d, e;
a.val = 3; a.left = &b; a.right = &c;
b.val = 9; b.left = NULL; b.right = NULL;
c.val = 20; c.left = &d; c.right = &e;
d.val = 15; d.left = NULL; d.right = NULL;
e.val = 7; e.left = NULL; e.right = NULL;
averageOfLevels(&a);
return 0;
}using System;
using System.Collections.Generic;
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
public IList<double> AverageOfLevels(TreeNode root) {
List<double> averages = new List<double>();
Queue<TreeNode> queue = new Queue<TreeNode>();
queue.Enqueue(root);
while (queue.Count > 0) {
int count = queue.Count;
double sum = 0;
for (int i = 0; i < count; i++) {
TreeNode node = queue.Dequeue();
sum += node.val;
if (node.left != null) queue.Enqueue(node.left);
if (node.right != null) queue.Enqueue(node.right);
}
averages.Add(sum / count);
}
return averages;
}
public static void Main(string[] args) {
TreeNode a = new TreeNode(3);
TreeNode b = new TreeNode(9);
TreeNode c = new TreeNode(20);
TreeNode d = new TreeNode(15);
TreeNode e = new TreeNode(7);
a.left = b;
a.right = c;
c.left = d;
c.right = e;
Solution solution = new Solution();
IList<double> result = solution.AverageOfLevels(a);
foreach (double avg in result) {
Console.Write(avg + " ");
}
}
}In the Python implementation, BFS is achieved using a deque as a queue. As each level is processed, the sum of node values is calculated, followed by the averaging of these values. This results in averages returned for each tree level.
Time Complexity: O(N), with N as the total nodes in the binary tree.
Space Complexity: O(M), where M is the maximum width of any level of the tree.
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.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def averageOfLevels(self, root):
self.sums = []
self.counts = []
self.dfs(root, 0)
return [s/c for s, c in zip(self.sums, self.counts)]
def dfs(self, node, level):
if not node:
return
if level < len(self.sums):
self.sums[level] += node.val
self.counts[level] += 1
else:
self.sums.append(node.val)
self.counts.append(1)
self.dfs(node.left, level + 1)
self.dfs(node.right, level + 1)
# Example Usage
if __name__ == '__main__':
a = TreeNode(3)
b = TreeNode(9)
c = TreeNode(20)
d = TreeNode(15)
e = TreeNode(7)
a.left = b
a.right = c
c.left = d
c.right = e
solution = Solution()
result = solution.averageOfLevels(a)
print(result)import java.util.*;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Solution {
public List<Double> averageOfLevels(TreeNode root) {
List<Double> averages = new ArrayList<>();
List<Long> levelSums = new ArrayList<>();
List<Integer> levelCounts = new ArrayList<>();
dfs(root, 0, levelSums, levelCounts);
for (int i = 0; i < levelSums.size(); i++) {
averages.add((double) levelSums.get(i) / levelCounts.get(i));
}
return averages;
}
private void dfs(TreeNode node, int level, List<Long> sums, List<Integer> counts) {
if (node == null) return;
if (level == sums.size()) {
sums.add((long) node.val);
counts.add(1);
} else {
sums.set(level, sums.get(level) + node.val);
counts.set(level, counts.get(level) + 1);
}
dfs(node.left, level + 1, sums, counts);
dfs(node.right, level + 1, sums, counts);
}
public static void main(String[] args) {
TreeNode a = new TreeNode(3);
TreeNode b = new TreeNode(9);
TreeNode c = new TreeNode(20);
TreeNode d = new TreeNode(15);
TreeNode e = new TreeNode(7);
a.left = b;
a.right = c;
c.left = d;
c.right = e;
Solution sol = new Solution();
List<Double> result = sol.averageOfLevels(a);
result.forEach(avg -> System.out.print(avg + " "));
}
}#include <iostream>
#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
void dfs(TreeNode* node, int level, vector<double>& sums, vector<int>& counts) {
if (!node) return;
if (level >= sums.size()) {
sums.push_back(node->val);
counts.push_back(1);
} else {
sums[level] += node->val;
counts[level]++;
}
dfs(node->left, level + 1, sums, counts);
dfs(node->right, level + 1, sums, counts);
}
vector<double> averageOfLevels(TreeNode* root) {
vector<double> sums;
vector<int> counts;
dfs(root, 0, sums, counts);
for (int i = 0; i < sums.size(); ++i) {
sums[i] /= counts[i];
}
return sums;
}
int main() {
/* Create Binary tree with nodes */
TreeNode a(3), b(9), c(20), d(15), e(7);
a.left = &b;
a.right = &c;
c.left = &d;
c.right = &e;
vector<double> result = averageOfLevels(&a);
for (double avg : result) {
cout << avg << " ";
}
return 0;
}class TreeNode {
constructor(val, left = null, right = null) {
this.val = val;
this.left = left;
this.right = right;
}
}
function averageOfLevels(root) {
const sums = [], counts = [];
dfs(root, 0, sums, counts);
return sums.map((sum, i) => sum / counts[i]);
}
function dfs(node, level, sums, counts) {
if (!node) return;
if (sums[level] === undefined) {
sums[level] = 0;
counts[level] = 0;
}
sums[level] += node.val;
counts[level]++;
dfs(node.left, level + 1, sums, counts);
dfs(node.right, level + 1, sums, counts);
}
// Example usage
const a = new TreeNode(3);
const b = new TreeNode(9);
const c = new TreeNode(20);
const d = new TreeNode(15);
const e = new TreeNode(7);
a.left = b;
a.right = c;
c.left = d;
c.right = e;
console.log(averageOfLevels(a));#include <stdio.h>
#include <stdlib.h>
#include <math.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
void dfs(struct TreeNode* node, int level, double* level_sums, int* level_counts, int* max_level) {
if (!node) return;
if (level > *max_level) {
(*max_level)++;
level_sums[level] = node->val;
level_counts[level] = 1;
} else {
level_sums[level] += node->val;
level_counts[level]++;
}
dfs(node->left, level + 1, level_sums, level_counts, max_level);
dfs(node->right, level + 1, level_sums, level_counts, max_level);
}
void averageOfLevels(struct TreeNode* root) {
double level_sums[10000] = {0};
int level_counts[10000] = {0};
int max_level = -1;
dfs(root, 0, level_sums, level_counts, &max_level);
for (int i = 0; i <= max_level; ++i) {
printf("%.5f ", level_sums[i] / level_counts[i]);
}
}
int main() {
/* Create Binary tree with nodes */
struct TreeNode a, b, c, d, e;
a.val = 3; a.left = &b; a.right = &c;
b.val = 9; b.left = NULL; b.right = NULL;
c.val = 20; c.left = &d; c.right = &e;
d.val = 15; d.left = NULL; d.right = NULL;
e.val = 7; e.left = NULL; e.right = NULL;
averageOfLevels(&a);
return 0;
}using System;
using System.Collections.Generic;
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
public IList<double> AverageOfLevels(TreeNode root) {
List<long> sums = new List<long>();
List<int> counts = new List<int>();
dfs(root, 0, sums, counts);
List<double> averages = new List<double>();
for (int i = 0; i < sums.Count; i++) {
averages.Add((double)sums[i] / counts[i]);
}
return averages;
}
private void dfs(TreeNode node, int level, List<long> sums, List<int> counts) {
if (node == null) return;
if (level == sums.Count) {
sums.Add(node.val);
counts.Add(1);
} else {
sums[level] += node.val;
counts[level]++;
}
dfs(node.left, level + 1, sums, counts);
dfs(node.right, level + 1, sums, counts);
}
public static void Main(string[] args) {
TreeNode a = new TreeNode(3);
TreeNode b = new TreeNode(9);
TreeNode c = new TreeNode(20);
TreeNode d = new TreeNode(15);
TreeNode e = new TreeNode(7);
a.left = b;
a.right = c;
c.left = d;
c.right = e;
Solution solution = new Solution();
IList<double> result = solution.AverageOfLevels(a);
foreach (double avg in result) {
Console.Write(avg + " ");
}
}
}The Python approach involves DFS for pre-order traversal to gather sums and counts of node values recursively. Calculated averages per level complete the method's goal.
Time Complexity: O(N) due to visiting all nodes once.
Space Complexity: O(H), where H is the tree's height, indicating recursion depth.
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.
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func averageOfLevels(root *TreeNode) []float64 {
q := []*TreeNode{root}
ans := []float64{}
for len(q) > 0 {
n := len(q)
s := 0
for i := 0; i < n; i++ {
root = q[0]
q = q[1:]
s += root.Val
if root.Left != nil {
q = append(q, root.Left)
}
if root.Right != nil {
q = append(q, root.Right)
}
}
ans = append(ans, float64(s)/float64(n))
}
return ans
}// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std::cell::RefCell;
use std::collections::VecDeque;
use std::rc::Rc;
impl Solution {
pub fn average_of_levels(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<f64> {
let mut ans = vec![];
let mut q = VecDeque::new();
if let Some(root_node) = root {
q.push_back(root_node);
}
while !q.is_empty() {
let n = q.len();
let mut s: i64 = 0;
for _ in 0..n {
if let Some(node) = q.pop_front() {
let node_borrow = node.borrow();
s += node_borrow.val as i64;
if let Some(left) = node_borrow.left.clone() {
q.push_back(left);
}
if let Some(right) = node_borrow.right.clone() {
q.push_back(right);
}
}
}
ans.push((s as f64) / (n as f64));
}
ans
}
}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.
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func averageOfLevels(root *TreeNode) []float64 {
s := []int{}
cnt := []int{}
var dfs func(root *TreeNode, i int)
dfs = func(root *TreeNode, i int) {
if root == nil {
return
}
if len(s) == i {
s = append(s, root.Val)
cnt = append(cnt, 1)
} else {
s[i] += root.Val
cnt[i]++
}
dfs(root.Left, i+1)
dfs(root.Right, i+1)
}
dfs(root, 0)
ans := []float64{}
for i, t := range s {
ans = append(ans, float64(t)/float64(cnt[i]))
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Breadth-First Search (BFS) Using Queue | Time Complexity: |
| Depth-First Search (DFS) With Pre-order Traversal | Time Complexity: |
| BFS | – |
| DFS | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Breadth-First Search (BFS) Using Queue | O(n) | O(w) | Best when computing values level-by-level in a tree; most intuitive approach |
| Depth-First Search (DFS) With Pre-order Traversal | O(n) | O(h) | Useful when recursion is preferred or when aggregating results per depth |
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.