Solution Explanation for Average of Levels in Binary Tree

This problem asks to calculate the average value of nodes at each level of a binary tree. Two common approaches are Breadth-First Search (BFS) and Depth-First Search (DFS).

Approach 1: Breadth-First Search (BFS)

BFS is well-suited for level-order traversal. We use a queue to process nodes level by level.

Algorithm:

1. Initialization: Create a queue q and add the root node. Initialize an empty list ans to store the average of each level.

2. Level Processing: While the queue is not empty:

   • Get the current level's size n. This represents the number of nodes at the current level.
   • Initialize s (sum) to 0.
   • Process n nodes:
     • Dequeue a node from q.
     • Add the node's value to s.
     • Enqueue the node's left and right children (if they exist).
   • Calculate the average s / n and append it to ans.

3. Return: Return ans.

Time Complexity: O(N), where N is the number of nodes. Each node is visited and processed once. Space Complexity: O(W), where W is the maximum width (number of nodes) of the tree. In the worst case (a complete binary tree), W can be proportional to N.

Approach 2: Depth-First Search (DFS)

DFS can also solve this, but requires a slightly different approach. We track the sum and count for each level separately.

Algorithm:

1. Initialization: Create two lists, s (sum) and cnt (count), both initially empty.

2. Recursive DFS: Implement a recursive function dfs(root, level):

   • Base Case: If root is null, return.
   • Level Check: If the current level is beyond the size of s and cnt, append 0 to both lists to create a new entry for this level.
   • Update: Add root.val to s[level] and increment cnt[level].
   • Recursion: Recursively call dfs for the left and right children, incrementing the level.

3. Average Calculation: After the DFS is complete, iterate through s and cnt, calculating the average s[i] / cnt[i] for each level and storing it in the result list.

Time Complexity: O(N), where N is the number of nodes. Each node is visited once. Space Complexity: O(H), where H is the height of the tree. This is due to the recursive call stack and the size of s and cnt which are proportional to the height of the tree. In the worst case (a skewed tree), H can be equal to N.

Code Examples (Python)

BFS:

from collections import deque
 
def averageOfLevels(root):
    q = deque([root])
    ans = []
    while q:
        level_size = len(q)
        level_sum = 0
        for _ in range(level_size):
            node = q.popleft()
            level_sum += node.val
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        ans.append(level_sum / level_size)
    return ans

DFS:

def averageOfLevels(root):
    sums = []
    counts = []
    def dfs(node, level):
        if not node:
            return
        if level >= len(sums):
            sums.append(0)
            counts.append(0)
        sums[level] += node.val
        counts[level] += 1
        dfs(node.left, level + 1)
        dfs(node.right, level + 1)
    dfs(root, 0)
    return [s / c for s, c in zip(sums, counts)]

These examples demonstrate both approaches. The choice between BFS and DFS depends on factors like the specific tree structure and memory constraints. For most cases, BFS is generally preferred due to its better space complexity for balanced or nearly balanced trees.