< Back





637. Average of Levels in Binary Tree

We're asked to return the average value of each level in a binary tree. We conduct BFS, sum the
nodes at each level, and maintain the number of nodes at each level. We update the average value of
each level and return it.

The solution is as follows:


  class Solution:
      def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
          ans, queue = [], [root]

          while queue:
              this_queue, queue = queue, []
              this_sum = count = 0

              for node in this_queue:
                  count += 1
                  this_sum += node.val

                  if node.left:
                      queue.append(node.left)
                  if node.right:
                      queue.append(node.right)

              ans.append(this_sum / count)

          return ans


_ Time Complexity:

  O(n) - We traverse O(n) nodes of the tree.

_ Space Complexity:

  O(n) - The queue can contain at most O(n) nodes of the tree.