### View *Average of Levels in Binary Tree* on LeetCode

## Statistics

**Time Spent Coding**

15 minutes

**Time Complexity**

O(n) - Every node in the tree must be visited, resulting in the O(n) time complexity.

**Space Complexity**

O(l) - The queue will have at most `l`

elements, where `l`

is the number of nodes in the largest level, resulting in the O(l) space complexity.

**Runtime Beats**

76.22% of other submissions

**Memory Beats**

73.90% of other sumbissions

## Explanation

The algorithm follows the breadth-first search algorithm and creates a queue of all nodes at the same level, iterates through exactly the number of elements at that level, and increments the `cur_sum`

variable while removing each node from the queue. At the same time, it is appending children nodes not equal to `None`

to the back of the queue to be iterated through on the next loop (the next level). Once the current level is exhausted, the algorithm divides the `cur_sum`

by the number of elements in that level to get the average and then adds that value to the result list. Finally, when no nodes are left in the queue, the algorithm returns the result list.

## Algorithm & Data Structure Used

**Breadth-first search -** A tree/matrix traversal algorithm that searches for elements with a given property. Create a queue of elements yet to be visited and then iterate through each level (similar properties) until there are no more elements of the same level.

**Binary Tree -** A rooted tree where every node has at most two children, the left and right children.

## Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# 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()
q.append(root)
res = []
while q:
cur_sum = 0
len_q = len(q)
for _ in range(len_q):
n = q.popleft()
cur_sum += n.val
if n.left: q.append(n.left)
if n.right: q.append(n.right)
res.append(cur_sum/len_q)
return res