Average of Levels in Binary Tree

▶

Steps

setup

Initialize queue with root node

The algorithm starts by checking if the root is null. Since it is not, it initializes the result list as empty and the queue with the root node (value 3).

💡 Initializing the queue with the root sets up the BFS traversal starting point.

Line:

result = []
queue = deque([root])

💡 The queue will hold nodes level by level, starting with the root.

fill_row

Start processing level 0

Begin processing the first level. Initialize level_sum to 0 and level_count to the number of nodes in the queue, which is 1.

💡 Knowing the number of nodes at the current level lets us process exactly that many nodes before moving to the next level.

Line:

level_sum = 0
level_count = len(queue)

💡 Level boundaries are defined by the queue size at the start of each iteration.

fill_cells

Dequeue node 3 and add its value to level_sum

Remove node 3 from the queue and add its value (3) to level_sum. Mark node 3 as active since it is being processed.

💡 Processing nodes one by one allows summing their values for the current level.

Line:

node = queue.popleft()
level_sum += node.val

💡 Dequeuing nodes in order ensures BFS level order traversal.

fill_cells

Enqueue children of node 3 (nodes 9 and 20)

Add node 3's left child (9) and right child (20) to the queue for processing in the next level.

💡 Adding children to the queue prepares the next level's nodes for processing.

Line:

if node.left:
    queue.append(node.left)
if node.right:
    queue.append(node.right)

💡 Children are enqueued in left-to-right order to preserve BFS order.

fill_row

Compute average for level 0 and append to result

Calculate the average for level 0 by dividing level_sum (3) by level_count (1), then append 3.0 to the result list.

💡 Computing the average immediately after processing a level keeps the result updated incrementally.

Line:

result.append(level_sum / level_count)

💡 The first level average is simply the root node's value.

fill_row

Start processing level 1

Initialize level_sum to 0 and level_count to 2, the number of nodes currently in the queue (nodes 9 and 20).

💡 Each level's node count is determined at the start to process exactly that many nodes.

Line:

level_sum = 0
level_count = len(queue)

💡 Level boundaries are maintained by queue size at each iteration.

fill_cells

Dequeue node 9 and add its value to level_sum

Remove node 9 from the queue and add its value (9) to level_sum. Mark node 9 as active.

💡 Processing each node updates the sum for the current level.

Line:

node = queue.popleft()
level_sum += node.val

💡 Nodes are processed in the order they were enqueued, preserving BFS order.

fill_cells

Node 9 has no children, so queue remains unchanged

Since node 9 has no left or right children, no new nodes are added to the queue.

💡 Leaf nodes do not add any new nodes to the queue, so the next level's nodes come from other siblings.

Line:

if node.left:
    queue.append(node.left)
if node.right:
    queue.append(node.right)

💡 Queue size decreases as leaf nodes are processed without adding children.

fill_cells

Dequeue node 20 and add its value to level_sum

Remove node 20 from the queue and add its value (20) to level_sum (which was 9). Mark node 20 as active.

💡 Continuing to process all nodes at the current level ensures the sum is complete.

Line:

node = queue.popleft()
level_sum += node.val

💡 All nodes at the current level contribute to the sum before computing the average.

fill_cells

Enqueue children of node 20 (nodes 15 and 7)

Add node 20's left child (15) and right child (7) to the queue for the next level processing.

💡 Adding children prepares the queue for the next level traversal.

Line:

if node.left:
    queue.append(node.left)
if node.right:
    queue.append(node.right)

💡 Next level nodes are queued in left-to-right order.

fill_row

Compute average for level 1 and append to result

Calculate the average for level 1 by dividing level_sum (29) by level_count (2), then append 14.5 to the result list.

💡 Computing the average after processing all nodes at a level updates the result incrementally.

Line:

result.append(level_sum / level_count)

💡 Level 1 average reflects the mean of nodes 9 and 20.

fill_row

Start processing level 2

Initialize level_sum to 0 and level_count to 2, the number of nodes in the queue (nodes 15 and 7).

💡 Each level's node count is determined at the start to process exactly that many nodes.

Line:

level_sum = 0
level_count = len(queue)

💡 Level boundaries are maintained by queue size at each iteration.

fill_cells

Dequeue node 15 and add its value to level_sum

Remove node 15 from the queue and add its value (15) to level_sum. Mark node 15 as active.

💡 Processing each node updates the sum for the current level.

Line:

node = queue.popleft()
level_sum += node.val

💡 Nodes are processed in the order they were enqueued, preserving BFS order.

fill_cells

Node 15 has no children, so queue remains unchanged

Since node 15 has no left or right children, no new nodes are added to the queue.

💡 Leaf nodes do not add any new nodes to the queue.

Line:

if node.left:
    queue.append(node.left)
if node.right:
    queue.append(node.right)

💡 Queue size decreases as leaf nodes are processed without adding children.

fill_cells

Dequeue node 7 and add its value to level_sum

Remove node 7 from the queue and add its value (7) to level_sum (which was 15). Mark node 7 as active.

💡 Processing all nodes at the level completes the sum for average calculation.

Line:

node = queue.popleft()
level_sum += node.val

💡 All nodes at the current level contribute to the sum before computing the average.

fill_cells

Node 7 has no children, so queue remains empty

Since node 7 has no children, no nodes are added to the queue. The queue is now empty, signaling traversal completion.

💡 When the queue is empty after processing a level, the BFS traversal ends.

Line:

if node.left:
    queue.append(node.left)
if node.right:
    queue.append(node.right)

💡 Empty queue means all nodes have been processed.

fill_row

Compute average for level 2 and append to result

Calculate the average for level 2 by dividing level_sum (22) by level_count (2), then append 11.0 to the result list.

💡 Final average calculation completes the result for the last level.

Line:

result.append(level_sum / level_count)

💡 Level 2 average reflects the mean of nodes 15 and 7.

reconstruct

Traversal complete, return result

The queue is empty, so the while loop ends and the algorithm returns the result list containing the averages of each level.

💡 Returning the result finalizes the BFS traversal and average calculation.

Line:

return result

💡 The final result contains the average values for all levels in order.

from collections import deque

def averageOfLevels(root):
    if not root:
        return []  # STEP 1
    result = []  # STEP 1
    queue = deque([root])  # STEP 1
    while queue:  # STEP 2,6,12
        level_sum = 0  # STEP 2,6,12
        level_count = len(queue)  # STEP 2,6,12
        for _ in range(level_count):  # STEP 3,7,9,13,15
            node = queue.popleft()  # STEP 3,7,9,13,15
            level_sum += node.val  # STEP 3,7,9,13,15
            if node.left:  # STEP 4,10,14,16
                queue.append(node.left)  # STEP 4,10
            if node.right:  # STEP 4,10,14,16
                queue.append(node.right)  # STEP 4,10
        result.append(level_sum / level_count)  # STEP 5,11,17
    return result  # STEP 18

📊

Average of Levels in Binary Tree - Watch the Algorithm Execute, Step by Step

Watching the algorithm step through each node and level helps you understand how BFS naturally groups nodes by depth and how averages are computed incrementally.

3920157

BFS Queue

N0 (L0)

3920157

BFS Queue

N0 (L0)

Current node: 0

3920157

3920157

BFS Queue

N1 (L1)N2 (L1)

3920157

BFS Queue

N1 (L1)N2 (L1)

Result: [3]

3920157

BFS Queue

N1 (L1)N2 (L1)

Result: [3]

Current node: 1

3920157

BFS Queue

N2 (L1)

Result: [3]

3920157

BFS Queue

N2 (L1)

Result: [3]

Current node: 2

3920157

Result: [3]

3920157

BFS Queue

N3 (L2)N4 (L2)

Result: [3]

3920157

BFS Queue

N3 (L2)N4 (L2)

Result: [3, 14.5]

3920157

BFS Queue

N3 (L2)N4 (L2)

Result: [3, 14.5]

Current node: 3

3920157

BFS Queue

N4 (L2)

Result: [3, 14.5]

3920157

BFS Queue

N4 (L2)

Result: [3, 14.5]

Current node: 4

3920157

Result: [3, 14.5]

3920157

Result: [3, 14.5]

3920157

Result: [3, 14.5, 11]

3920157

Result: [3, 14.5, 11]

Return: [3,14.5,11]

Key Takeaways

✓ BFS naturally groups nodes by level, making it ideal for level-based computations like averages.

This insight is hard to see from code alone because the queue operations abstract away the level grouping.

✓ The queue size at the start of each iteration defines the current level's boundary.

Understanding this helps clarify how the algorithm processes exactly one level at a time.

✓ Children are enqueued in left-to-right order, preserving the natural left-to-right traversal within each level.

This ordering ensures the averages correspond to the correct level nodes in the correct order.

Practice

1. You are given a binary tree and need to output the nodes grouped by their vertical columns, from leftmost column to rightmost, preserving the top-to-bottom order within each column. Which approach guarantees an optimal solution for this problem?

easy

A. Depth-first search (DFS) collecting nodes by column and sorting them by row and value afterwards

B. Greedy traversal picking nodes with minimum column index first without sorting or queue

C. Dynamic programming to compute vertical sums and then reconstruct node order

D. Breadth-first search (BFS) with column tracking using an ordered map to maintain column order and insertion order for nodes

Solution

1. Step 1: Understand problem requirements

   The problem requires grouping nodes by vertical columns and preserving top-to-bottom order within each column.

2. Step 2: Evaluate approaches

   DFS with sorting (A) works but is less efficient; greedy (B) fails to preserve order; DP (D) is unrelated. BFS with column tracking and ordered map (C) naturally preserves order and column sorting efficiently.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   BFS with ordered map preserves vertical order and top-to-bottom traversal [OK]

Hint: BFS with ordered map preserves vertical and top-down order [OK]

Common Mistakes:

• Assuming DFS alone preserves top-to-bottom order without sorting
• Using greedy approach ignoring node order within columns

2. Consider the following Python code for vertical order traversal of a binary tree:

from collections import deque
from sortedcontainers import SortedDict

def verticalOrder(root):
    if not root:
        return []
    col_table = SortedDict()
    queue = deque([(root, 0)])
    while queue:
        node, col = queue.popleft()
        if col not in col_table:
            col_table[col] = []
        col_table[col].append(node.val)
        if node.left:
            queue.append((node.left, col - 1))
        if node.right:
            queue.append((node.right, col + 1))
    return list(col_table.values())

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

root = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
print(verticalOrder(root))

What is the output of this code?

easy

A. [[9], [3, 15], [20], [7]]

B. [[9], [3, 20, 15], [7]]

C. [[9], [3], [15, 20], [7]]

D. [[9], [3], [20, 15], [7]]

Solution

1. Step 1: Trace queue and col_table updates

   Start with root (3, col=0). Append 3 to col 0. Enqueue left child (9, col=-1), right child (20, col=1).

2. Step 2: Process nodes in BFS order

   Process (9, -1): append 9 to col -1. No children. Process (20, 1): append 20 to col 1. Enqueue (15, 0), (7, 2). Process (15, 0): append 15 to col 0. Process (7, 2): append 7 to col 2.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Columns sorted: -1:[9], 0:[3,15], 1:[20], 2:[7] matches [[9], [3, 15], [20], [7]] [OK]

Hint: BFS preserves top-to-bottom order in each column [OK]

Common Mistakes:

• Mixing order of nodes in same column
• Misassigning column indices for children

3. Consider the following code snippet implementing the optimal recursive approach to connect next pointers in a binary tree. Given the tree below:

       1
      / \
     2   3
    /     \
   4       5

After calling connect(root), what is the value of root.left.right.next?

class Node:
    def __init__(self, val=0, left=None, right=None, next=None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next

def connect(root):
    if not root:
        return None

    if root.left and root.right:
        root.left.next = root.right

    next_node = root.next
    while next_node:
        if next_node.left:
            next_child = next_node.left
            break
        if next_node.right:
            next_child = next_node.right
            break
        next_node = next_node.next
    else:
        next_child = None

    if root.right:
        root.right.next = next_child
    elif root.left:
        root.left.next = next_child

    connect(root.right)
    connect(root.left)

    return root

easy

A. Node with value 4

B. Node with value 5

C. null

D. Node with value 3

Solution

1. Step 1: Trace connections at root (node 1)

   root.left (2) next -> root.right (3). root.right (3) next -> null (no next at root level).

2. Step 2: Trace connections at node 2

   Node 2 has left child 4, no right child. Its next is 3, which has right child 5. So 4.next -> 5.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   4.next points to 5, not null or 3 [OK]

Hint: Next pointers connect nodes across parents at same level [OK]

Common Mistakes:

• Assuming 4.next is null because 2 has no right child
• Confusing next pointers with parent pointers
• Thinking next points to parent or sibling's parent

4. You are given a binary tree and need to determine if it is symmetric around its center. Which approach best guarantees an optimal solution by comparing nodes in pairs using a queue and terminating early when asymmetry is detected?

easy

A. Recursive depth-first traversal comparing left subtree to left subtree

B. Dynamic programming storing subtree symmetry states bottom-up

C. Greedy traversal checking only the root and immediate children

D. Iterative breadth-first search using a queue to compare mirrored node pairs with early termination

Solution

1. Step 1: Understand the problem requirement

   The problem requires checking if a tree is symmetric, which means the left subtree is a mirror reflection of the right subtree.

2. Step 2: Identify the approach that compares mirrored nodes efficiently

   Using an iterative BFS with a queue to compare pairs of nodes from left and right subtrees simultaneously allows early detection of asymmetry and avoids unnecessary traversal.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Iterative BFS with paired nodes and early termination is optimal for symmetry check [OK]

Hint: Symmetry requires mirrored node pair comparison [OK]

Common Mistakes:

• Comparing left subtree to left subtree instead of mirrored right subtree
• Using greedy checks that miss deeper asymmetry
• Assuming symmetry can be checked by root and immediate children only

5. The following code attempts to count good nodes in a binary tree using iterative DFS. Identify the line containing the subtle bug that causes incorrect counting.

medium

A. Line checking if node.val > max_val instead of >= max_val

B. Line updating max_val with max(max_val, node.val)

C. Line pushing node.right onto the stack

D. Line returning count at the end

Solution

1. Step 1: Examine condition for counting good nodes

   The condition uses strictly greater (node.val > max_val), but problem definition includes equality (>=).

2. Step 2: Understand impact of strict inequality

   This causes undercounting when node.val equals max_val, missing some good nodes.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Changing > to >= fixes counting [OK]

Hint: Check if condition uses >= not > for counting [OK]

Common Mistakes:

• Using > instead of >=
• Not updating max_val before pushing children
• Ignoring null root case