Average of Levels in Binary Tree

Problem Statement

Given the root of a binary tree, return an array of the average value of the nodes on each level of the tree.

Answers within 10^-5 of the actual answer will be accepted as correct.

What to notice first

• You need to process each level and calculate the average of all nodes in that level.
• Both BFS and DFS can solve this, but with different approaches.
• Be careful with floating-point precision when calculating averages.

Examples

Input	Output	Explanation
[3,9,20,null,null,15,7]	[3.00000,14.50000,7.50000]	Level 1: 3/1=3; Level 2: (9+20)/2=14.5; Level 3: (15+7)/2=7.5
[3,9,20]	[3.00000,14.50000]	Level 1: 3; Level 2: (9+20)/2=14.5

Visualized Examples

Example 1:       3           Level 1: avg = 3
              /     \
             9      20       Level 2: avg = (9+20)/2 = 14.5
                  /    \
                 15     7    Level 3: avg = (15+7)/2 = 7.5

Example 2:       3           Level 1: avg = 3
              /     \
             9      20       Level 2: avg = 14.5

Constraints

• The number of nodes in the tree is in the range [1, 10^4].
• -2^31 <= Node.val <= 2^31 - 1

Real-World Applications

Where this pattern appears

• Data center monitoring — calculate average resource usage per layer.
• Sales analytics — compute average sales by tier or department level.
• Performance metrics — track average response times by request depth.
• Educational institutions — calculate average scores by grade level.
• Healthcare systems — compute average patient metrics by care level.

Complexity Comparison

Approach	Time	Space	Best When
BFS Level-Order	O(n)	O(w)	Clear level-by-level processing
DFS with Level Tracking	O(n)	O(h)	Smaller trees; prefer recursion

Where h = height, w = max width

Which approach should you learn first?

• Pick BFS Level-Order for intuitive, clear level-by-level aggregation.
• Pick DFS with Level Tracking if you prefer recursive solutions.

Level-by-Level

BFS Level-Order

O(n) time · O(w) space

Recursive

DFS with Level Tracking

O(n) time · O(h) space

Approach 1: BFS Level-Order (Recommended)

★ Recommended

Use a queue to traverse level by level. For each level, sum all node values, then divide by the count.

⏱ Time O(n) Visit all nodes 💾 Space O(w) Queue width at widest level

Step-by-step Example

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

Level 1: sum=3, count=1, avg=3.0 Level 2: sum=29, count=2, avg=14.5 Level 3: sum=22, count=2, avg=7.5

Pseudocode

function averageOfLevelsBFS(root):
    result = []
    queue = [root]

    while queue is not empty:
        levelSize = length of queue
        levelSum = 0

        for i = 0 to levelSize - 1:
            node = queue.dequeue()
            levelSum += node.val

            if node.left exists:
                queue.enqueue(node.left)
            if node.right exists:
                queue.enqueue(node.right)

        result.append(levelSum / levelSize)

    return result

Solution Code

Python

average_of_levels_in_binary_tree_bfs.py

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


def averageOfLevels(root: Optional[TreeNode]) -> List[float]:
    """BFS level-order traversal to calculate averages."""
    if not root:
        return []

    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


if __name__ == "__main__":
    root1 = TreeNode(3)
    root1.left = TreeNode(9)
    root1.right = TreeNode(20)
    root1.right.left = TreeNode(15)
    root1.right.right = TreeNode(7)

    result1 = averageOfLevels(root1)
    print(f"Averages: {result1}")  # Expected: [3.0, 14.5, 7.5]

C++

average_of_levels_in_binary_tree_bfs.cpp

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

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

        queue<TreeNode*> q;
        q.push(root);

        while (!q.empty()) {
            int levelSize = q.size();
            long long levelSum = 0;

            for (int i = 0; i < levelSize; i++) {
                TreeNode* node = q.front();
                q.pop();
                levelSum += node->val;

                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }

            result.push_back((double)levelSum / levelSize);
        }

        return result;
    }
};

int main() {
    Solution sol;
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(9);
    root->right = new TreeNode(20);
    root->right->left = new TreeNode(15);
    root->right->right = new TreeNode(7);

    vector<double> result = sol.averageOfLevels(root);
    cout << "Averages: ";
    for (double val : result) cout << val << " ";
    cout << endl;

    return 0;
}

Java

average_of_levels_in_binary_tree_bfs.java

import java.util.*;

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

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            long levelSum = 0;

            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                levelSum += node.val;

                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }

            result.add((double) levelSum / levelSize);
        }

        return result;
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);

        List<Double> result = sol.averageOfLevels(root);
        System.out.println("Averages: " + result);
    }
}

JavaScript

average_of_levels_in_binary_tree_bfs.js

function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

function averageOfLevels(root) {
    const result = [];
    if (!root) return result;

    const queue = [root];

    while (queue.length > 0) {
        const levelSize = queue.length;
        let levelSum = 0;

        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift();
            levelSum += node.val;

            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }

        result.push(levelSum / levelSize);
    }

    return result;
}

if (require.main === module) {
    const root = new TreeNode(3);
    root.left = new TreeNode(9);
    root.right = new TreeNode(20);
    root.right.left = new TreeNode(15);
    root.right.right = new TreeNode(7);

    const result = averageOfLevels(root);
    console.log("Averages:", result);
}

module.exports = averageOfLevels;

Rust

average_of_levels_in_binary_tree_bfs.rs

use std::cell::RefCell;
use std::collections::VecDeque;
use std::rc::Rc;

#[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,
        }
    }
}

pub fn average_of_levels(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<f64> {
    let mut result = Vec::new();
    if root.is_none() {
        return result;
    }

    let mut queue = VecDeque::new();
    queue.push_back(root.unwrap());

    while !queue.is_empty() {
        let level_size = queue.len();
        let mut level_sum: i64 = 0;

        for _ in 0..level_size {
            let node = queue.pop_front().unwrap();
            let node_ref = node.borrow_mut();

            level_sum += node_ref.val as i64;

            if let Some(left) = node_ref.left.clone() {
                queue.push_back(left);
            }
            if let Some(right) = node_ref.right.clone() {
                queue.push_back(right);
            }
        }

        result.push(level_sum as f64 / level_size as f64);
    }

    result
}

Go

average_of_levels_in_binary_tree_bfs.go

package main

import "fmt"

type TreeNode struct {
  Val   int
  Left  *TreeNode
  Right *TreeNode
}

func AverageOfLevels(root *TreeNode) []float64 {
  result := []float64{}
  if root == nil {
    return result
  }

  queue := []*TreeNode{root}

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

    for i := 0; i < levelSize; i++ {
      node := queue[0]
      queue = queue[1:]
      levelSum += int64(node.Val)

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

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

  return result
}

func main() {
  root := &TreeNode{Val: 3}
  root.Left = &TreeNode{Val: 9}
  root.Right = &TreeNode{Val: 20}
  root.Right.Left = &TreeNode{Val: 15}
  root.Right.Right = &TreeNode{Val: 7}

  result := AverageOfLevels(root)
  fmt.Println("Averages:", result)
}

Approach 2: DFS with Level Tracking

🎯 Interview Favourite

Use DFS to traverse the tree, tracking the current level. Maintain lists of sums and counts per level, then calculate averages.

⏱ Time O(n) Visit all nodes 💾 Space O(h) Recursion call stack

Step-by-step Example

DFS visits nodes in pre-order: 3 (L0), 9 (L1), 20 (L1), 15 (L2), 7 (L2)

Accumulate:

• Level 0: sum=3, count=1
• Level 1: sum=29, count=2
• Level 2: sum=22, count=2

Average: [3.0, 14.5, 7.5]

Pseudocode

function averageOfLevelsDFS(root):
    sums = []
    counts = []

    function dfs(node, level):
        if node is null:
            return

        if level == length of sums:
            sums.append(0)
            counts.append(0)

        sums[level] += node.val
        counts[level] += 1

        dfs(node.left, level + 1)
        dfs(node.right, level + 1)

    dfs(root, 0)

    result = []
    for i in range(length of sums):
        result.append(sums[i] / counts[i])

    return result

Solution Code

Python

average_of_levels_in_binary_tree_dfs.py

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


def averageOfLevels(root: Optional[TreeNode]) -> List[float]:
    """DFS with level tracking to calculate averages."""
    sums = []
    counts = []

    def dfs(node: Optional[TreeNode], level: int) -> None:
        if not node:
            return

        if level == len(sums):
            sums.append(0)
            counts.append(0)

        sums[level] += node.val
        counts[level] += 1

        dfs(node.left, level + 1)
        dfs(node.right, level + 1)

    dfs(root, 0)

    return [sums[i] / counts[i] for i in range(len(sums))]


if __name__ == "__main__":
    root1 = TreeNode(3)
    root1.left = TreeNode(9)
    root1.right = TreeNode(20)
    root1.right.left = TreeNode(15)
    root1.right.right = TreeNode(7)

    result1 = averageOfLevels(root1)
    print(f"Averages: {result1}")  # Expected: [3.0, 14.5, 7.5]

C++

average_of_levels_in_binary_tree_dfs.cpp

#include <iostream>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
private:
    void dfs(TreeNode* node, int level, vector<long long>& sums, vector<int>& counts) {
        if (!node) return;

        if (level == sums.size()) {
            sums.push_back(0);
            counts.push_back(0);
        }

        sums[level] += node->val;
        counts[level]++;

        dfs(node->left, level + 1, sums, counts);
        dfs(node->right, level + 1, sums, counts);
    }

public:
    vector<double> averageOfLevels(TreeNode* root) {
        vector<long long> sums;
        vector<int> counts;
        dfs(root, 0, sums, counts);

        vector<double> result;
        for (int i = 0; i < sums.size(); i++) {
            result.push_back((double)sums[i] / counts[i]);
        }
        return result;
    }
};

int main() {
    Solution sol;
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(9);
    root->right = new TreeNode(20);
    root->right->left = new TreeNode(15);
    root->right->right = new TreeNode(7);

    vector<double> result = sol.averageOfLevels(root);
    cout << "Averages: ";
    for (double val : result) cout << val << " ";
    cout << endl;

    return 0;
}

Java

average_of_levels_in_binary_tree_dfs.java

import java.util.*;

public class Solution {
    private void dfs(TreeNode node, int level, List<Long> sums, List<Integer> counts) {
        if (node == null) return;

        if (level == sums.size()) {
            sums.add(0L);
            counts.add(0);
        }

        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 List<Double> averageOfLevels(TreeNode root) {
        List<Long> sums = new ArrayList<>();
        List<Integer> counts = new ArrayList<>();
        dfs(root, 0, sums, counts);

        List<Double> result = new ArrayList<>();
        for (int i = 0; i < sums.size(); i++) {
            result.add((double) sums.get(i) / counts.get(i));
        }
        return result;
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);

        List<Double> result = sol.averageOfLevels(root);
        System.out.println("Averages: " + result);
    }
}

JavaScript

average_of_levels_in_binary_tree_dfs.js

function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

function averageOfLevels(root) {
    const sums = [];
    const counts = [];

    function dfs(node, level) {
        if (!node) return;

        if (level === sums.length) {
            sums.push(0);
            counts.push(0);
        }

        sums[level] += node.val;
        counts[level]++;

        dfs(node.left, level + 1);
        dfs(node.right, level + 1);
    }

    dfs(root, 0);

    return sums.map((sum, i) => sum / counts[i]);
}

if (require.main === module) {
    const root = new TreeNode(3);
    root.left = new TreeNode(9);
    root.right = new TreeNode(20);
    root.right.left = new TreeNode(15);
    root.right.right = new TreeNode(7);

    const result = averageOfLevels(root);
    console.log("Averages:", result);
}

module.exports = averageOfLevels;

Rust

average_of_levels_in_binary_tree_dfs.rs

use std::cell::RefCell;
use std::rc::Rc;

#[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,
        }
    }
}

pub fn average_of_levels(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<f64> {
    let mut sums: Vec<i64> = Vec::new();
    let mut counts: Vec<i32> = Vec::new();

    fn dfs(
        node: &Option<Rc<RefCell<TreeNode>>>,
        level: usize,
        sums: &mut Vec<i64>,
        counts: &mut Vec<i32>,
    ) {
        if let Some(n) = node {
            let n_ref = n.borrow();

            if level == sums.len() {
                sums.push(0);
                counts.push(0);
            }

            sums[level] += n_ref.val as i64;
            counts[level] += 1;

            dfs(&n_ref.left, level + 1, sums, counts);
            dfs(&n_ref.right, level + 1, sums, counts);
        }
    }

    dfs(&root, 0, &mut sums, &mut counts);

    sums.iter()
        .enumerate()
        .map(|(i, &sum)| sum as f64 / counts[i] as f64)
        .collect()
}

Go

average_of_levels_in_binary_tree_dfs.go

package main

import "fmt"

type TreeNode struct {
  Val   int
  Left  *TreeNode
  Right *TreeNode
}

func AverageOfLevels(root *TreeNode) []float64 {
  sums := []int64{}
  counts := []int{}

  var dfs func(*TreeNode, int)
  dfs = func(node *TreeNode, level int) {
    if node == nil {
      return
    }

    if level == len(sums) {
      sums = append(sums, 0)
      counts = append(counts, 0)
    }

    sums[level] += int64(node.Val)
    counts[level]++

    dfs(node.Left, level+1)
    dfs(node.Right, level+1)
  }

  dfs(root, 0)

  result := make([]float64, len(sums))
  for i := 0; i < len(sums); i++ {
    result[i] = float64(sums[i]) / float64(counts[i])
  }

  return result
}

func main() {
  root := &TreeNode{Val: 3}
  root.Left = &TreeNode{Val: 9}
  root.Right = &TreeNode{Val: 20}
  root.Right.Left = &TreeNode{Val: 15}
  root.Right.Right = &TreeNode{Val: 7}

  result := AverageOfLevels(root)
  fmt.Println("Averages:", result)
}

Approach 3: BFS Iterative Solution

🎯 Interview Favourite

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(n) Efficient space usage

Pseudocode

function approach3():
    // Implementation approach goes here

Solution Code

Python

average_of_levels_in_binary_tree_bfs_iterative.py

"""
Solution for Average of Levels in Binary Tree
"""

def solve():
    """Implementation for approach 3 of Average of Levels in Binary Tree"""
    pass

if __name__ == "__main__":
    print("Solution ready")

C++

average_of_levels_in_binary_tree_bfs_iterative.cpp

#include <bits/stdc++.h>
using namespace std;

// Solution for Average of Levels in Binary Tree
// Approach 3: Implementation

int main() {{
    // Main implementation goes here
    return 0;
}}

Java

AverageOfLevelsInBinaryTreeBfsIterative.java

/**
 * Solution for Average of Levels in Binary Tree
 * Approach 3
 */
public class AverageOfLevelsInBinaryTreeBfsIterative {{

    public static void main(String[] args) {{
        // Implementation goes here
    }}
}}

JavaScript

average_of_levels_in_binary_tree_bfs_iterative.js

/**
 * Solution for Average of Levels in Binary Tree
 * Approach 3
 */

function solve() {{
    // Implementation goes here
}}

module.exports = solve;

Rust

average_of_levels_in_binary_tree_bfs_iterative.rs

/// Solution for Average of Levels in Binary Tree
/// Approach 3

fn main() {{
    println!("Solution implementation");
}}

Go

average_of_levels_in_binary_tree_bfs_iterative.go

package main

import "fmt"

// Solution for Average of Levels in Binary Tree
// Approach 3

func main() {{
    fmt.Println("Solution implementation")
}}

Common Mistakes

Watch for these pitfalls

• Integer division instead of floating-point. Use double/float for the average calculation.
• Forgetting to initialize sum/count arrays. Make sure you create them as you encounter new levels.
• Off-by-one in level tracking. Ensure levels are indexed correctly.
• Not handling empty trees. Return an empty list for null input.

Related Problems

• Binary Tree Level Order Traversal ↗ Medium #102
• Binary Tree Zigzag Level Order Traversal ↗ Medium #103
• Binary Tree Right Side View ↗ Medium #199
• Maximum Depth of Binary Tree ↗ Easy #104

Interview Tips

Key trade-offs to discuss

• Floating-point precision: Discuss rounding strategies and acceptable error margins.
• Space vs code clarity: BFS is clearer; DFS saves space on wide trees.
• Follow-ups to expect: sum of levels, product of levels, or filtering by conditions.

← Previous
#636 Exclusive Time of Functions Next
#638 Shopping Offers →