Find Largest Value in Each Tree Row: BFS Level Maximums

Given the root of a binary tree, return an array of the largest value in each row of the tree (0-indexed). This is LeetCode 515: Find Largest Value in Each Tree Row.

For example, given root = [1, 3, 2, 5, 3, null, 9], the output is [1, 3, 9]. Row 0 has just 1, row 1 has 3 and 2 (max is 3), and row 2 has 5, 3, and 9 (max is 9).

The approach

If you have solved Binary Tree Level Order Traversal (LeetCode 102), this problem is a direct reduction. Instead of collecting every value at each level into a sublist, you track only the maximum value you see while draining that level.

The plan is BFS with level-size snapshots:

1. Seed a queue with the root.
2. At the start of each level, record the queue size. That tells you how many nodes belong to the current row.
3. Dequeue that many nodes one by one, updating a running maximum as you go. For each node, enqueue its children.
4. When the inner loop finishes, the running maximum is the largest value for that row. Append it to the result.
5. Repeat until the queue is empty.

Step-by-step walkthrough

Notice the pattern. At each row, you initialize the max to negative infinity (or the first node's value), then compare every node in that row. Once you have drained all nodes for that level, the running max is your answer for the row. Children enqueued during the pass belong to the next row.

The code

from collections import deque

def largest_values(root):
    if not root:
        return []
    result = []
    queue = deque([root])
    while queue:
        level_size = len(queue)
        level_max = float("-inf")
        for _ in range(level_size):
            node = queue.popleft()
            level_max = max(level_max, node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level_max)
    return result

Here is what each part does:

• queue = deque([root]) seeds the queue with the root node. Row 0 always has exactly one node.
• level_size = len(queue) captures how many nodes are in the current row before draining begins.
• level_max = float("-inf") initializes the running maximum. Using negative infinity means any node value will replace it on the first comparison.
• The for loop dequeues exactly level_size nodes, updates the max, and enqueues children. When the loop finishes, the queue holds only nodes from the next row.
• result.append(level_max) stores the largest value for the completed row and moves on.

Complexity analysis

Time: O(n). Every node is enqueued and dequeued exactly once. The max() comparison inside the loop is O(1) per node, so the total work across all levels is O(n).

Space: O(n). The queue can hold up to n/2 nodes at once. This happens at the widest level of a complete binary tree, where the bottom row contains roughly half of all nodes. The result array stores one value per level, which is O(h) where h is the tree height, but the queue dominates.

Building blocks

This problem is built on two reusable patterns:

1. BFS level-by-level processing. The template snapshots the queue size at the start of each level and drains exactly that many nodes. This is the same template used in level order traversal, right side view, and zigzag traversal. Once you internalize the snapshot trick, every level-aware BFS problem uses the same skeleton.

2. Running maximum. Inside the inner loop, you maintain a single variable that tracks the largest value seen so far in the current level. This is the same reduce pattern you would use for finding the max of any sequence - initialize with negative infinity and update on each element.

Edge cases

• Empty tree (root is None): return an empty list []. The guard clause at the top handles this before the queue is created.
• Single node (no children): return [root.val]. The root is the only node at row 0, so the level max is its value. The queue empties after one iteration.
• All negative values: works correctly because level_max starts at negative infinity. Even if every node has a negative value like -100, the comparisons still find the largest among them.
• Skewed tree (every node has only one child): each row has exactly one node, so the max at each level is just that node's value. The result is a list of every node value from top to bottom.

From understanding to recall

You just traced through a BFS solution that reduces each tree row to its maximum value. The pattern is clean: snapshot the queue size, drain the level, track the max. It makes sense right now. But when you face a variation like Average of Levels (LeetCode 637) or Minimum Depth (LeetCode 111) in an interview next month, will you reconstruct the level-size snapshot from memory? Will you remember to initialize the max correctly?

Understanding a pattern and being able to reproduce it under pressure are different skills. Spaced repetition bridges that gap. You practice typing the BFS level-by-level template from memory at increasing intervals - first after a day, then three days, then a week. Each repetition reinforces the snapshot trick, the inner loop structure, and the per-level aggregation until it becomes automatic.

BFS level-by-level is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling them individually with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Binary Tree Level Order Traversal - Same BFS level-by-level pattern, collecting all nodes instead of just the max
• Binary Tree Right Side View - BFS variant that picks the last (rightmost) node per level instead of the maximum
• Binary Tree Zigzag Level Order Traversal - Level-order traversal with alternating direction