# LC 637. Average of Levels in Binary Tree

### [Problem link](https://leetcode.com/problems/average-of-levels-in-binary-tree/)

###### tags: `leedcode` `easy` `python` `c++` `Binary Tree`

Given the <code>root</code> of a binary tree, return the average value of the nodes on each level in the form of an array. Answers within <code>10^-5</code> of the actual answer will be accepted.

**Example 1:**
<img alt="" src="https://assets.leetcode.com/uploads/2021/03/09/avg1-tree.jpg" style="width: 277px; height: 302px;" />

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:**
<img alt="" src="https://assets.leetcode.com/uploads/2021/03/09/avg2-tree.jpg" style="width: 292px; height: 302px;" />

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 <code>[1, 10⁴]</code>.
- <code>-2³¹ <= Node.val <= 2³¹ - 1</code>

## Solution 1
#### 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]:
        res = []

        if not root:
            return res

        q = deque([root])

        while q:
            size_q = len(q)
            tmp_sum = 0
            for i in range(size_q):
                node = q.popleft()
                tmp_sum += node.val
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            res.append(tmp_sum / size_q)

        return res

#### C++

class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        vector<double> res;
        queue<TreeNode*> q;

        if (root != nullptr) {
            q.push(root);
        }
        while (!q.empty()) {
            int size = q.size();
            long int level_sum = 0;

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

                if (node->left) {
                    q.emplace(node->left);
                }
                if (node->right) {
                    q.emplace(node->right);
                }
            }
            res.push_back((double)level_sum / (double)size);
        }
        return res;
    }
};

>### Complexity
>n = number of tree's node
>l = max number of tree level's node
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(n) | O(1) |

## Note
x