We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Average of Levels in Binary Tree

Difficulty: Easy

Problem Description

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.

Key Insights

  • The problem requires calculating the average of node values at each level of the binary tree.
  • A level-order traversal (BFS) can be used to access nodes level by level.
  • We need to maintain a running total of node values and a count of nodes at each level to compute the average.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes in the binary tree, as we visit each node once. Space Complexity: O(w), where w is the maximum width of the tree, which is the maximum number of nodes at any level.

Solution

To solve this problem, we can use a breadth-first search (BFS) approach. We will utilize a queue data structure to traverse the tree level by level. At each level, we will keep track of the sum of the node values and the number of nodes. After processing all nodes at a level, we calculate the average and store it in the result list.

Code Solutions

from collections import deque

def averageOfLevels(root):
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        level_sum = 0
        level_count = len(queue)
        
        for _ in range(level_count):
            node = queue.popleft()
            level_sum += node.val
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        average = level_sum / level_count
        result.append(average)
    
    return result
← Back to All Questions