# Average of Levels in Binary Tree
**Difficulty:** EASY
[External](https://leetcode.com/problems/average-of-levels-in-binary-tree)
Canonical: https://scaleengineer.com/dsa/problems/average-of-levels-in-binary-tree
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Tree, Binary Tree
---
## Problem
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:**

![](https://assets.glich.co/dsa/average-of-levels-in-binary-tree/image0.jpg) 

**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:**

![](https://assets.glich.co/dsa/average-of-levels-in-binary-tree/image1.jpg) 

**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`

# Approaches
## Breadth-First Search (BFS)
This approach uses Breadth-First Search (BFS), which naturally processes the tree level by level. We use a queue to keep track of nodes to visit. For each level, we iterate through all nodes on that level, calculate their sum and count, then compute the average and add it to our result list. This is a very intuitive and direct way to solve the problem.
**Time:** O(N), where N is the number of nodes. Each node is enqueued and dequeued exactly once. · **Space:** O(W), where W is the maximum width of the binary tree. This is the maximum number of nodes that can be in the queue at any one time. In the worst case of a complete binary tree, W can be up to N/2, making the space complexity O(N).
**Pros:** Very intuitive and direct for level-order problems.; Processes one level completely before moving to the next.
**Cons:** Can be less space-efficient than DFS, especially for balanced or "wide" trees where the maximum width W can be large (up to O(N)).
### Explanation
BFS is an iterative algorithm that is perfectly suited for problems requiring level-by-level processing.
The algorithm proceeds as follows:
1. Create a list `averages` to store the result. If the `root` is null, return an empty list.
2. Initialize a `Queue` (e.g., a `LinkedList`) and add the `root` node to it.
3. Enter a loop that continues as long as the queue is not empty. This loop processes one level of the tree in each iteration.
4. Inside the loop, first, get the number of nodes currently in the queue. This value, `levelSize`, represents the number of nodes at the current level.
5. Initialize a variable `levelSum` to 0.0 to accumulate the sum of node values for the current level.
6. Start an inner loop that runs `levelSize` times. In this loop, we process each node of the current level.
7. Dequeue a node, add its value to `levelSum`, and enqueue its non-null children (left and right).
8. After the inner loop finishes, all nodes for the current level have been processed. Calculate the average for the level (`levelSum / levelSize`) and add it to the `averages` list.
9. The outer loop then continues to the next level.
Once the queue is empty, all levels have been processed, and the `averages` list contains the final result.
```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

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

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

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            double levelSum = 0.0;
            for (int i = 0; i < levelSize; i++) {
                TreeNode currentNode = queue.poll();
                levelSum += currentNode.val;
                if (currentNode.left != null) {
                    queue.offer(currentNode.left);
                }
                if (currentNode.right != null) {
                    queue.offer(currentNode.right);
                }
            }
            averages.add(levelSum / levelSize);
        }

        return averages;
    }
}
```
### Algorithm
1. If `root` is null, return an empty list.
2. Initialize a result list `averages` and a `Queue` with the `root` node.
3. Loop while the `queue` is not empty:
    a. Get the current size of the queue, `levelSize`.
    b. Initialize `levelSum = 0.0`.
    c. Loop `levelSize` times:
        i. Dequeue a `node`.
        ii. Add `node.val` to `levelSum`.
        iii. Enqueue `node.left` if it's not null.
        iv. Enqueue `node.right` if it's not null.
    d. Calculate the average `levelSum / levelSize` and add it to `averages`.
4. Return `averages`.

## Depth-First Search (DFS)
This approach uses a recursive Depth-First Search (DFS) traversal to visit every node in the tree. While traversing, we keep track of the current node's level. We use auxiliary data structures, typically two lists, to store the aggregated sum of node values and the count of nodes for each level. This method can be more space-efficient than BFS for certain tree structures.
**Time:** O(N), where N is the number of nodes in the tree. We visit each node exactly once during the traversal, and then iterate through the levels (at most H levels) once. Total time is O(N + H) = O(N). · **Space:** O(H), where H is the height of the tree. This space is used by the recursion stack and the `sums`/`counts` lists, both of which have a size equal to the height of the tree. For a balanced tree, this is O(log N), which is more efficient than BFS's O(N) space. However, in the worst case of a skewed tree, H can be N, making the space complexity O(N).
**Pros:** More space-efficient than BFS for balanced or "fat" trees, where the height H is much smaller than the maximum width W. The average space complexity for a random tree is O(log N).
**Cons:** Less intuitive for a level-by-level problem compared to BFS.; Requires an extra pass at the end to compute the averages from the sums and counts.; Can be less space-efficient than BFS for "tall and skinny" trees.
### Explanation
Although BFS is more direct for level-order problems, DFS can also solve it efficiently. The key is to pass the level information down during the recursion.
We'll define a helper function, say `dfs(node, level)`, which takes the current node and its level as input.
We'll also need two lists, `sums` (to store the sum of values for each level) and `counts` (to store the number of nodes for each level).
The `dfs` function works as follows:
1. Base case: If the current `node` is `null`, we simply return.
2. When visiting a node at a certain `level`, we check if this is the first time we are visiting this level. If `level` is equal to the current size of the `sums` list, it means we need to create a new entry for this level. We append the node's value to `sums` and `1` to `counts`.
3. If the `level` has been visited before, we simply update the existing entries: `sums[level] += node.val` and `counts[level] += 1`.
4. Recursively call the `dfs` function for the left and right children, incrementing the level for each call: `dfs(node.left, level + 1)` and `dfs(node.right, level + 1)`.
The main function will initialize the process by calling `dfs(root, 0)`.
After the traversal is complete, the `sums` and `counts` lists are fully populated. We then iterate through them to compute the average for each level (`sums[i] / counts[i]`) and build our final result list.
```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> sums = new ArrayList<>();
        List<Integer> counts = new ArrayList<>();
        dfs(root, 0, sums, counts);

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

    private void dfs(TreeNode node, int level, List<Double> sums, List<Integer> counts) {
        if (node == null) {
            return;
        }

        if (level < sums.size()) {
            sums.set(level, sums.get(level) + node.val);
            counts.set(level, counts.get(level) + 1);
        } else {
            sums.add(1.0 * node.val);
            counts.add(1);
        }

        dfs(node.left, level + 1, sums, counts);
        dfs(node.right, level + 1, sums, counts);
    }
}
```
### Algorithm
1. Initialize two lists: `sums` to store the sum of node values per level and `counts` to store the number of nodes per level.
2. Define a recursive helper function `dfs(node, level, sums, counts)`.
3. In `dfs`, if `node` is null, return.
4. If `level` is a new level (i.e., `level == sums.size()`), add `(double)node.val` to `sums` and `1` to `counts`.
5. Otherwise, update `sums.set(level, sums.get(level) + node.val)` and `counts.set(level, counts.get(level) + 1)`.
6. Recursively call `dfs` for `node.left` and `node.right` with `level + 1`.
7. Start the traversal by calling `dfs(root, 0, sums, counts)`.
8. After the traversal, create a result list `averages`.
9. Iterate from `i = 0` to `sums.size() - 1` and calculate `averages.add(sums.get(i) / counts.get(i))`.
10. Return `averages`.

# Solutions
### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public List < Double > averageOfLevels ( TreeNode root ) { List < Double > ans = new ArrayList <>(); Deque < TreeNode > q = new ArrayDeque <>(); q . offer ( root ); while (! q . isEmpty ()) { int n = q . size (); long s = 0 ; for ( int i = 0 ; i < n ; ++ i ) { root = q . pollFirst (); s += root . val ; if ( root . left != null ) { q . offer ( root . left ); } if ( root . right != null ) { q . offer ( root . right ); } } ans . add ( s * 1.0 / n ); } return ans ; } }
```

### JavaScript

```javascript
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @return {number[]} */ var averageOfLevels =
  function (root) {
    let q = [root];
    let ans = [];
    while (q.length) {
      const n = q.length;
      let s = 0;
      for (let i = 0; i < n; ++i) {
        root = q.shift();
        s += root.val;
        if (root.left) {
          q.push(root.left);
        }
        if (root.right) {
          q.push(root.right);
        }
      }
      ans.push(s / n);
    }
    return ans;
  };

```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector < double > averageOfLevels ( TreeNode * root ) { queue < TreeNode *> q { { root } }; vector < double > ans ; while ( ! q . empty ()) { int n = q . size (); long long s = 0 ; for ( int i = 0 ; i < n ; ++ i ) { root = q . front (); q . pop (); s += root -> val ; if ( root -> left ) q . push ( root -> left ); if ( root -> right ) q . push ( root -> right ); } ans . push_back ( s * 1.0 / n ); } return ans ; } };
```

### Python

```python
# 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 ]: q = deque ([ root ]) ans = [] while q : s , n = 0 , len ( q ) for _ in range ( n ): root = q . popleft () s += root . val if root . left : q . append ( root . left ) if root . right : q . append ( root . right ) ans . append ( s / n ) return ans
```