637. Average of Levels in Binary Tree
Model: qwen2.5-coder:14b
Topics: Tree
FAANG asked: 1
Acceptance rate: 66.1%
Problem Breakdown
The problem requires calculating the average value of nodes at each level in a binary tree. Given the root of the tree, we need to return an array where each element represents the average value of all nodes at that level. The input is a binary tree node structure, and the output is a list of floating-point numbers representing the averages.
Inputs:
root: A binary tree node representing the root of the tree.
Outputs:
- A list of floating-point numbers where each number is the average value of nodes at that level in the tree.
Implicit Constraints or Tricky Edge Cases:
- The tree can be empty (though this is not possible given the constraints).
- Nodes can have negative values.
- The number of nodes is between 1 and 10^4, which affects the choice of algorithm for efficiency.
Intuition
A brute-force approach would involve traversing the entire tree to collect all node values at each level and then calculating the average. This approach would be inefficient in terms of both time and space complexity because it requires storing all node values before computing averages.
The key insight is to use a breadth-first search (BFS) approach, which naturally processes nodes level by level. By using a queue to manage nodes at each level, we can efficiently compute the average for each level without needing to store all node values beforehand.
Approach
-
Initialize Data Structures:
- Use a queue to facilitate BFS traversal.
- Use a list to store the average values of each level.
-
BFS Traversal:
- Start by adding the root node to the queue.
- While the queue is not empty, process all nodes at the current level:
- Determine the number of nodes at the current level (
level_size). - Initialize a variable to accumulate the sum of node values at this level.
- For each node at the current level:
- Dequeue the node and add its value to the accumulator.
- Enqueue the left child if it exists.
- Enqueue the right child if it exists.
- Calculate the average for the current level by dividing the accumulated sum by
level_size. - Append this average to the result list.
- Determine the number of nodes at the current level (
-
Return Result:
- After processing all levels, return the list of averages.
Complexity Analysis
- Time Complexity: O(n), where n is the number of nodes in the tree. Each node is processed exactly once.
- Space Complexity: O(m), where m is the maximum number of nodes at any level in the tree (the width of the tree). This is due to the queue used for BFS.
Solution
from collections import deque
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def averageOfLevels(root: TreeNode) -> list[float]:
if not root:
return []
queue = deque([root])
averages = []
while queue:
level_size = len(queue)
level_sum = 0
for _ in range(level_size):
node = queue.popleft()
level_sum += node.val
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
averages.append(level_sum / level_size)
return averages
Edge Cases Handled
- Single Node Tree: The root is the only node, so the average is simply its value.
- Balanced vs. Skewed Trees: The BFS approach handles both cases efficiently by processing nodes level by level.
- Negative Node Values: The sum and average calculations handle negative values correctly.
- Large Number of Nodes: The BFS approach ensures that the solution remains efficient even with up to 10^4 nodes.
The provided solution is correct, efficient, and clear. It handles all edge cases as described in the problem statement.