Coding Interview PatternsFind Largest Value in Each Tree Row
MediumTree Breadth-First Search

Find Largest Value in Each Tree Row

Explanation & Solution

Practice Problem

Description

Given the root of a binary tree, return an array of the largest value in each row of the tree (0-indexed).

Examples

Example 1:

```tree

[1, 3, 2, 5, 3, null, 9]

`

Input:root = [1, 3, 2, 5, 3, null, 9]
0
1
1
3
2
2
3
5
4
3
5
null
6
9
Output:[1, 3, 9]
0
1
1
3
2
9

Explanation:

  • Row 0: max(1) = 1
  • Row 1: max(3, 2) = 3
  • Row 2: max(5, 3, 9) = 9

Example 2:

```tree

[1, 2, 3]

`

Input:root = [1, 2, 3]
0
1
1
2
2
3
Output:[1, 3]
0
1
1
3

Example 3:

Input: root = []

Output: []

Constraints

  • The number of nodes in the tree is in the range [0, 10⁴]
  • -2³¹ <= Node.val <= 2³¹ - 1

Approach

Tree Breadth-First Search pattern

1. Handle Empty Tree

  • If root is null, return an empty array []

2. Initialize BFS

  • Create a result array to hold the largest value per row
  • Create a queue initialized with the root node
  • Use a head pointer for efficient dequeuing

3. Process Level by Level

  • While there are nodes in the queue:
  • Calculate levelSize — the number of nodes at the current level
  • Initialize max to -Infinity
  • For each node in the current level:
  • Update max if the node's value is larger
  • Enqueue left and right children if they exist
  • Push max into result

4. Return Result

  • After BFS completes, result contains the largest value from each row
  • Return result

Key Insight

  • BFS naturally groups nodes by level, making it straightforward to find the maximum per level
  • We simply track the running maximum while processing each level
Time
O(n)every node is visited exactly once
Space
O(n)the queue may hold up to an entire level of nodes

Visualization

Input:
DFS Traversal[1, 3, 2, 5, 3, 9]
132539
output0

Press play to start DFS traversal

CurrentIn stackComplete
13 steps

Solution Code

Previous
Even Odd Tree
Next
Check Completeness of a Binary Tree