Find Largest Value in Each Tree Row
Problem
Given the root of a binary tree, return a list of the largest values in each row of the tree.
- The number of nodes in the tree is in the range [0, 10⁴]
- −2³¹ ≤ Node.val ≤ 2³¹ - 1
Example
root = [1,3,2,5,3,null,9][1,3,9]The tree has three rows: the first row contains [1], so the largest value is 1. The second row contains [3, 2], with the largest value 3. The third row contains [5, 3, 9], with the largest value 9. The algorithm uses a queue to perform a breadth-first search (BFS), processing nodes level by level. At each level, it tracks the maximum node value. After processing all nodes at a level, it appends the maximum to the result list. This continues until all levels are processed.
Approach
Straightforward Solution
A naive approach might attempt a depth-first search (DFS) with tracking of levels and updating maximums, but this requires careful management of recursion and level state. Alternatively, a brute-force approach might collect all nodes per level first and then compute maximums, which is less efficient in space and time.
Core Observation
The problem requires processing nodes level by level and extracting the maximum value per level. This naturally maps to a breadth-first search (BFS) traversal, where nodes are visited in order of their depth.
Path to Optimal
PreviewRecognizing that BFS inherently processes nodes level by level, the optimal approach uses a queue to hold nodes of the current level. By iterating over the queue size at each step, the algorithm isolates nodes belonging to the same level…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewUse a queue initialized with the root node. While the queue is not empty, determine the number of nodes at the current level (queue size)…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n)
Each node is enqueued and dequeued exactly once during the BFS traversal, resulting in linear time proportional to the number of nodes.
Space
O(w)
The auxiliary space is proportional to the maximum width of the tree (the largest number of nodes at any level), which is the maximum size of the queue during traversal.
Pattern Spotlight
BFS (Level-Order Traversal with Aggregation)
When a problem requires processing nodes level by level and aggregating information per level, use BFS with a queue and iterate over the current queue size to isolate levels, enabling efficient per-level computations.
Solution
| 1 | class Solution: |
| 2 | def largestValues(self, root: Optional[TreeNode]) -> List[int]: |
| 3 | if not root: |
| 4 | return [] |
| 5 | |
| 6 | res = [] |
| 7 | q = deque([root]) |
| 8 | |
| 9 | while q: |
| 10 | level_size = len(q) |
| 11 | level_max = float("-inf") |
| 12 | |
| 13 | for _ in range(level_size): |
| 14 | node = q.popleft() |
| 15 | level_max = max(level_max, node.val) |
| 16 | |
| 17 | if node.left: |
| 18 | q.append(node.left) |
| 19 | if node.right: |
| 20 | q.append(node.right) |
| 21 | |
| 22 | res.append(level_max) |
| 23 | |
| 24 | return res |
Step-by-Step Solution
Return Empty List for Null Root to Handle Edge Case
| 3 | if not root: |
| 4 | return [] |
Objective
To immediately return an empty list if the input tree is empty, avoiding unnecessary computation.
Key Insight
Checking for a null root upfront handles the edge case where the tree has no nodes. This early return prevents the BFS logic from running on an empty structure, simplifying the rest of the code and ensuring correctness.
Interview Quick-Check
State & Boundaries
Return [] immediately if root is None, as there are no levels to process.
Initialize Result List and Queue with Root Node
To prepare the data structures needed for BFS traversal: a list to store maximum values per level and a queue initialized with the root node.
Process Each Level by Iterating Over Current Queue Size
To traverse the tree level by level by iterating exactly over the number of nodes currently in the queue, which represents one level.
Track Maximum Value per Level and Enqueue Children
To update the maximum value found at the current level and enqueue the left and right children of each node for the next level's processing.
Append Level Maximum to Result After Processing Each Level
To record the largest value found at the current level into the result list after all nodes of that level have been processed.
Return the List of Largest Values per Level
To return the final list containing the largest values found at each level of the tree after BFS traversal completes.
5 more steps with full analysis available on Pro.
Line Analysis
This solution has 3 Critical lines interviewers watch for.
if not root:Check if the root is null to handle the empty tree edge case.
This early return prevents unnecessary processing and correctly handles the case where the input tree has no nodes.
return []Return an empty list when the tree is empty.
Returning an empty list is the correct output when there are no levels to process, ensuring the function's contract is fulfilled.
level_max = max(level_max, node.val)Update the maximum value for the current level with the current node's value.
Updating level_max with the maximum of the current value and node.val is the critical operation that ensures the algorithm correctly identifies the largest value per level.
Full line-by-line criticality + rationale for all 16 lines available on Pro.
Test Your Understanding
Why does iterating over the queue size at each step correctly isolate nodes belonging to the same tree level?
See the answer with Pro.
Related Problems
BFS pattern
Don't just read it. Drill it.
Reconstruct Find Largest Value in Each Tree Row from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Find Largest Value in Each Tree Row drill