Average of Levels in Binary Tree

Tree BFS

Problem

Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array.

For example:

Input:
    3
   / \
  9  20
    /  \
   15   7
Output: [3, 14.5, 11]
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].

Thought Process

• Have a "sum" variable to add all the numbers in the queue then divide by the queue length and append this to our results list

Solution

from collections import deque
class Solution:
    def averageOfLevels(self, root: TreeNode) -> List[float]:
        if root is None:
            return []
        
        result = []
        queue = deque()
        queue.append(root)
        
        while queue:
            sums = 0
            levelSize = len(queue)
            
            for _ in range(levelSize):
                currentNode = queue.popleft()
                sums+=currentNode.val
                
                if currentNode.left:
                    queue.append(currentNode.left)
                if currentNode.right:
                    queue.append(currentNode.right)
            result.append(sums/levelSize)
        return result
        
#Time: O(n)
#Space: O(n)