algoadvance

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

Example 1:

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].

Note:

Clarifying Questions

  1. What is the structure of the input?
    • The input is a binary tree.
  2. What should be returned?
    • An array of floats representing the average value of nodes at each level.
  3. Are there any constraints on the tree size?
    • No specific constraints are mentioned, but it should fit memory limitations for typical 32-bit systems.

Strategy

To solve this problem, we can perform a level order traversal (BFS) of the binary tree. By summing the values of nodes at each level and then dividing by the number of nodes at that level, we can compute the average for each level.

Steps:

  1. Initialize an empty result list to store the averages.
  2. Use a queue to facilitate level order traversal. Initially, add the root to the queue.
  3. While the queue is not empty:
    • Determine the number of nodes at the current level.
    • For each node at the current level, sum their values and add their children to the queue.
    • Compute the average for the current level and append it to the result list.
  4. Return the result list.

Code

Here’s the implementation in Python:

from collections import deque

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def averageOfLevels(self, root: TreeNode):
        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)
            
            result.append(level_sum / level_count)
        
        return result

Time Complexity

The time complexity of this solution is (O(n)), where (n) is the number of nodes in the binary tree. This is because each node is processed exactly once during the level order traversal.

Space Complexity

The space complexity is also (O(n)), which is the maximum number of nodes that can be stored in the queue at any one time. In the worst-case scenario (a completely balanced binary tree), this would be around (n/2).

This completes the solution strategy along with the code for the given problem.

Try our interview co-pilot at AlgoAdvance.com