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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Average of Levels in Binary Tree

Number: 637

Difficulty: Easy

Paid? No

Companies: Google, Meta, Qualcomm

Problem Description

Given the root of a binary tree, compute the average value of the nodes on each level and return these averages in an array. Each level's average is computed by summing all node values on that level and dividing by the number of nodes present.

Key Insights

  • Use level-order traversal (BFS) to process each level of the tree.
  • A queue helps to efficiently traverse the tree level by level.
  • For each level, track the number of nodes and the cumulative sum to compute the average.
  • Edge cases include handling an empty tree (though given constraints confirm at least one node).

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes in the tree because each node is processed exactly once.
Space Complexity: O(n) in the worst-case (e.g., when the tree is completely balanced, the last level might contain O(n/2) nodes).

Solution

The solution employs a breadth-first search (BFS) using a queue to traverse the tree level by level. For each level, it calculates the sum of node values and the count of nodes. By dividing the cumulative sum by the count, it obtains the average for that level, which is then added to the result list. This approach efficiently computes the required averages with a clear focus on level-wise processing.

Code Solutions

# Python solution using BFS (level-order traversal)
from collections import deque

def averageOfLevels(root):
    # List to store the average of each level
    result = []
    # Deque for efficient popping from the left
    queue = deque([root])
    
    # Process until no more nodes exist in the current level
    while queue:
        level_size = len(queue)
        level_sum = 0
        # Iterate through nodes on the current level
        for _ in range(level_size):
            node = queue.popleft()  # Remove node from the queue
            level_sum += node.val   # Add node's value to current level sum
            # Enqueue left and right children if they exist
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        # Compute the average and add it to the result list
        result.append(level_sum / level_size)
    return result
← Back to All Questions