LeetCode 637: Average of Levels in Binary Tree Solution in Python – A Step-by-Step Guide

What Is LeetCode 637: Average of Levels in Binary Tree?

In LeetCode 637: Average of Levels in Binary Tree, you’re given the root of a binary tree (nodes with val, left, and right attributes), and your task is to compute the average value of nodes at each level, returning these averages in a list. Levels are numbered from 0 (root) downward, and you calculate the mean of all node values at each depth. For example, with [3, 9, 20, null, null, 15, 7], the averages are [3.0, 14.5, 11.0] for levels 0, 1, and 2. This problem tests your ability to traverse a binary tree and process nodes by level.

Problem Statement

• Input:
• root: Root node of a binary tree.
• Output: A list of floats—average value at each level.
• Rules:
• Compute average of node values per level.
• Levels start at 0 (root).
• Return results in order from top to bottom.

Constraints

• Number of nodes: 1 to 10⁴.
• -2³¹ ≤ Node.val ≤ 2³¹ - 1.

Examples

• Input: root = [3, 9, 20, null, null, 15, 7]
• Output: [3.0, 14.5, 11.0]
• Level 0: 3 → 3.0.
• Level 1: (9 + 20) / 2 = 14.5.
• Level 2: (15 + 7) / 2 = 11.0.
• Input: root = [1]
• Output: [1.0] (Single node)
• Input: root = [3, 9, 20, 15, 7]
• Output: [3.0, 14.5, 11.0] (Same tree, different notation)

These examples set the tree—let’s solve it!

Understanding the Problem: Averaging Levels

To solve LeetCode 637: Average of Levels in Binary Tree in Python, we need to traverse a binary tree, group nodes by level, compute the average value at each level, and return these averages in a list. A naive approach—traversing multiple times per level—would be O(n * h), where h is height, inefficient for large trees. Since we need level-wise processing, we can use BFS or DFS efficiently. We’ll explore:

• Best Solution (BFS with Queue): O(n) time, O(w) space—fast and intuitive (w = max width).
• Alternative Solution (DFS with Level Tracking): O(n) time, O(h) space—recursive but requires extra bookkeeping.

Let’s start with the BFS solution, breaking it down for beginners.

Best Solution: Breadth-First Search with Queue

Why This Is the Best Solution

The BFS with queue approach is the top choice for LeetCode 637 because it’s efficient—O(n) time with O(w) space—and naturally processes the tree level by level using a queue, making it perfect for averaging nodes at each depth. It fits constraints (n ≤ 10⁴) and is straightforward to understand, especially for level-order tasks. It’s like walking the tree floor by floor, tallying as you go!

How It Works

Think of this as a level sweeper:

• Step 1: Initialize Queue:
• Start with root in a queue.
• Step 2: Process Levels:
• For each level:
• Dequeue all nodes at current level.
• Compute sum and count.
• Enqueue children for next level.
• Step 3: Compute Averages:
• Divide sum by count per level, store in result list.
• Step 4: Return Result:
• Return list of averages.

It’s like a tree leveler—queue and average!

Step-by-Step Example

Example: root = [3, 9, 20, null, null, 15, 7]

• Step 1: Queue = [(3, 0)], result = [].
• Step 2: Process:
• Level 0:
• Dequeue (3, 0), sum = 3, count = 1.
• Enqueue (9, 1), (20, 1).
• Avg = 3 / 1 = 3.0, result = [3.0].
• Level 1:
• Dequeue (9, 1), (20, 1), sum = 9 + 20 = 29, count = 2.
• Enqueue (15, 2), (7, 2).
• Avg = 29 / 2 = 14.5, result = [3.0, 14.5].
• Level 2:
• Dequeue (15, 2), (7, 2), sum = 15 + 7 = 22, count = 2.
• Avg = 22 / 2 = 11.0, result = [3.0, 14.5, 11.0].
• Step 3: Queue empty, done.
• Output: [3.0, 14.5, 11.0].

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

from collections import deque

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) -> List[float]:
        # Step 1: Initialize queue and result
        if not root:
            return []
        queue = deque([root])
        result = []

        # Step 2: Process levels with BFS
        while queue:
            level_size = len(queue)
            level_sum = 0

            # Process all nodes at current level
            for _ in range(level_size):
                node = queue.popleft()
                level_sum += node.val

                # Enqueue children
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

            # Step 3: Compute average for this level
            result.append(level_sum / level_size)

        # Step 4: Return averages
        return result

• Line 1: Import deque for queue.
• Lines 4-7: TreeNode class (standard).
• Lines 12-15: Init: Check null root, start queue with root.
• Lines 18-31: BFS:
• Process level: Dequeue nodes, sum values, enqueue kids.
• Compute average, append to result.
• Time Complexity: O(n)—visit each node once.
• Space Complexity: O(w)—queue holds max width.

This is like a level averager—queue and compute!

Alternative Solution: Depth-First Search with Level Tracking

Why an Alternative Approach?

The DFS with level tracking uses recursion to traverse the tree—O(n) time, O(h) space (h = height). It’s more recursive, tracking sums and counts per level in a depth-first manner, but requires extra data structures. It’s like climbing the tree and noting totals as you go!

How It Works

Picture this as a tree climber:

• Step 1: Init lists for sums and counts per level.
• Step 2: DFS traversal:
• Recursively visit nodes, track level, update sums/counts.
• Step 3: Compute averages from lists.
• Step 4: Return result.

It’s like a recursive surveyor—climb and tally!

Step-by-Step Example

Example: Same as above

• Step 1: Sums = [], Counts = [].
• Step 2: DFS:
• Node 3, level 0: Sums = [3], Counts = [1].
• Node 9, level 1: Sums = [3, 9], Counts = [1, 1].
• Node 20, level 1: Sums = [3, 29], Counts = [1, 2].
• Node 15, level 2: Sums = [3, 29, 15], Counts = [1, 2, 1].
• Node 7, level 2: Sums = [3, 29, 22], Counts = [1, 2, 2].
• Step 3: Averages = [3/1, 29/2, 22/2] = [3.0, 14.5, 11.0].
• Output: [3.0, 14.5, 11.0].

Code for DFS Approach

class Solution:
    def averageOfLevels(self, root: TreeNode) -> List[float]:
        # Step 1: Initialize lists for sums and counts
        sums = []
        counts = []

        # Step 2: DFS to collect sums and counts
        def dfs(node, level):
            if not node:
                return
            # Extend lists if level is new
            while len(sums) <= level:
                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)

        # Step 3: Compute averages
        return [s / c for s, c in zip(sums, counts)]

• Lines 4-5: Init lists for sums and counts.
• Lines 8-17: DFS:
• Recurse, update sums/counts by level.
• Line 20: Compute averages with list comprehension.
• Time Complexity: O(n)—visit each node.
• Space Complexity: O(h)—recursion stack.

It’s a recursive tallier—climb and count!

Comparing the Two Solutions

• BFS (Best):
• Pros: O(n) time, O(w) space, level-order simplicity.
• Cons: Wider space for broad trees.
• DFS (Alternative):
• Pros: O(n) time, O(h) space, recursive elegance.
• Cons: Extra bookkeeping.

BFS wins for clarity and fit.

Additional Examples and Edge Cases

• Input: [1, null, 2]
• Output: [1.0, 2.0].
• Input: [0]
• Output: [0.0].

Both handle these well.

Complexity Breakdown

• BFS: Time O(n), Space O(w).
• DFS: Time O(n), Space O(h).

BFS is optimal for level tasks.

Key Takeaways

• BFS: Queue simplicity—smart!
• DFS: Recursive depth—clear!
• Trees: Levels are fun.
• Python Tip: Queues rock—see Python Basics.

Final Thoughts: Average Those Levels

LeetCode 637: Average of Levels in Binary Tree in Python is a fun tree traversal challenge. BFS with a queue offers speed and clarity, while DFS provides a recursive twist. Want more? Try LeetCode 102: Binary Tree Level Order Traversal or LeetCode 104: Maximum Depth of Binary Tree. Ready to survey? Head to Solve LeetCode 637 on LeetCode and average those levels today!