LeetCode 515: Find Largest Value in Each Tree Row

Problem Restatement

We are given the root of a binary tree.

For every depth level in the tree, we need to find the largest node value on that row.

Return the results as an array where:

answer[i]

is the maximum value on depth i.

The official problem asks us to return the largest value in each row of a binary tree. (leetcode.com)

Input and Output

Function shape:

class Solution:
    def largestValues(self, root: Optional[TreeNode]) -> List[int]:
        ...

Examples

Example 1:

        1
       / \
      3   2
     / \   \
    5   3   9

The levels are:

So the answer is:

[1, 3, 9]

Example 2:

    1

There is only one level.

So the answer is:

[1]

First Thought: Process the Tree Level by Level

The problem asks for information grouped by tree rows.

This naturally suggests level-order traversal.

BFS processes nodes one depth level at a time.

While processing one level, we can track the largest value seen so far.

Key Insight

At the beginning of each BFS level:

len(queue)

tells us how many nodes belong to that level.

So we can:

1. Process exactly those nodes
2. Compute the maximum value among them
3. Append the result

Then continue to the next level.

Algorithm

Handle the empty tree case:

if not root:
    return []

Initialize:

queue = deque([root])

While the queue is not empty:

1. Let level_size = len(queue)
2. Initialize the current level maximum
3. Process exactly level_size nodes
4. Update the level maximum
5. Add child nodes to the queue
6. Append the level maximum to the answer list

Return the answer list.

Correctness

BFS visits nodes level by level.

At the start of each iteration, the queue contains exactly the nodes from the current tree row.

The algorithm processes every node on that row exactly once and updates the running maximum whenever a larger value is found.

After all nodes on that level are processed, the recorded maximum equals the largest value in that row.

The algorithm repeats this process for every level of the tree, so the final answer list contains exactly one maximum value for each row in top-to-bottom order.

Therefore the algorithm returns the correct result.

Complexity

Here:

In the worst case, w = O(n).

Implementation

from typing import Optional, List
from collections import deque

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def largestValues(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []

        answer = []
        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)

            answer.append(level_max)

        return answer

Code Explanation

Handle the empty tree:

if not root:
    return []

Initialize the BFS queue:

queue = deque([root])

The answer list stores one maximum per level:

answer = []

At each iteration:

level_size = len(queue)

gives the number of nodes in the current row.

Initialize the maximum for this level:

level_max = float("-inf")

Process all nodes in the current level:

for _ in range(level_size):

Update the maximum value:

level_max = max(level_max, node.val)

Add children for the next BFS level:

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

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

After finishing the level:

answer.append(level_max)

stores the largest value for that row.

Testing

def test_largest_values():
    s = Solution()

    # Tree:
    #         1
    #        / \
    #       3   2
    #      / \   \
    #     5   3   9
    root = TreeNode(1)
    root.left = TreeNode(3)
    root.right = TreeNode(2)
    root.left.left = TreeNode(5)
    root.left.right = TreeNode(3)
    root.right.right = TreeNode(9)

    assert s.largestValues(root) == [1, 3, 9]

    # Single node
    root = TreeNode(7)
    assert s.largestValues(root) == [7]

    # Negative values
    root = TreeNode(-1)
    root.left = TreeNode(-5)
    root.right = TreeNode(-2)

    assert s.largestValues(root) == [-1, -2]

    # Left-skewed tree
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.left.left = TreeNode(3)

    assert s.largestValues(root) == [1, 2, 3]

    print("all tests passed")

Test meaning: