# 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:

```python
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](https://leetcode.com/problems/find-largest-value-in-each-tree-row/?utm_source=chatgpt.com))

## Input and Output

| Item | Meaning |
|---|---|
| Input | The root of a binary tree |
| Output | A list of integers |
| `answer[i]` | Largest value on level `i` |

Function shape:

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

## Examples

Example 1:

```text
        1
       / \
      3   2
     / \   \
    5   3   9
```

The levels are:

| Level | Values | Maximum |
|---|---|---:|
| 0 | `1` | `1` |
| 1 | `3, 2` | `3` |
| 2 | `5, 3, 9` | `9` |

So the answer is:

```python
[1, 3, 9]
```

Example 2:

```text
    1
```

There is only one level.

So the answer is:

```python
[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:

```python
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:

```python
if not root:
    return []
```

Initialize:

```python
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

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each node is visited once |
| Space | `O(w)` | The queue stores one level at a time |

Here:

| Symbol | Meaning |
|---|---|
| `n` | Number of nodes |
| `w` | Maximum tree width |

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

## Implementation

```python
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:

```python
if not root:
    return []
```

Initialize the BFS queue:

```python
queue = deque([root])
```

The answer list stores one maximum per level:

```python
answer = []
```

At each iteration:

```python
level_size = len(queue)
```

gives the number of nodes in the current row.

Initialize the maximum for this level:

```python
level_max = float("-inf")
```

Process all nodes in the current level:

```python
for _ in range(level_size):
```

Update the maximum value:

```python
level_max = max(level_max, node.val)
```

Add children for the next BFS level:

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

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

After finishing the level:

```python
answer.append(level_max)
```

stores the largest value for that row.

## Testing

```python
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:

| Test | Why |
|---|---|
| Mixed balanced tree | Standard multi-level case |
| Single node | Minimum valid tree |
| Negative values | Confirms correct maximum logic |
| Left-skewed tree | One node per level |