Average Of Levels In Binary Tree - Leetcode Solution

The problem "Average Of Levels In Binary Tree" on LeetCode asks us to calculate the average value of each level in a given binary tree. We need to return the result as an array.

Approach:

The first step is to traverse the binary tree level by level utilizing the Breadth First Search technique (BFS).

While traversing the tree, we need to calculate the average of nodes at each level.

To keep track of nodes on one level, we need to add all child nodes of each parent node in a list that represents the nodes on that level.

We will continue to traverse the tree level by level until we reach the last level. Additionally, we will use a list to store the average value of each level.

Finally, we will return the list after all the levels have been traversed.

Below is the algorithm in detail:

1. Create an empty queue, which will serve as a data structure for BFS.

2. Add the root node in the queue.

3. Create an empty list to store the average value of each level.

4. Loop until the queue is not empty. Inside the loop:

a. Set the value of the sum to 0 and size to the size of the current level.

b. Loop through the level until all nodes have been processed. Inside the loop:

i. Remove the current node from the queue.

ii. Add the value of the current node to the sum.

iii. Enqueue the left and right children of the current node, if present.

c. Calculate the average value of the level by dividing the sum by its size.

d. Append the average value to the list of level averages.

5. Return the level averages list.

Code:

Here's the Python code for solving this problem:

from collections import deque

class Solution:
    def averageOfLevels(self, root: TreeNode) -> List[float]:
        if not root:
            return []
        
        queue = deque([root])
        level_averages = []
        
        while queue:
            level_sum, level_size = 0, len(queue)
            for i in range(level_size):
                current_node = queue.popleft()
                level_sum += current_node.val
                
                if current_node.left:
                    queue.append(current_node.left)
                if current_node.right:
                    queue.append(current_node.right)
            
            level_averages.append(level_sum / level_size)
        
        return level_averages

Complexity Analysis:

The time complexity of the above code is O(N), where N is the number of nodes in the binary tree. It is because we traverse each node only once using BFS.

The space complexity of the code is O(M), where M is the maximum number of nodes on a single level of the tree. This is because, at any moment, the queue will hold nodes from a single level.

1