What pattern does Find Largest Value in Each Tree Row use?

The Pattern: BFS (Level-Order Traversal with Aggregation) The Heuristic: 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.

Find Largest Value in Each Tree Row

Q: What is the time complexity of Find Largest Value in Each Tree Row?

O(n). Each node is enqueued and dequeued exactly once during the BFS traversal, resulting in linear time proportional to the number of nodes.

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

Input: root = [1,3,2,5,3,null,9]

Output: [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

Recognizing 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. During this iteration, it tracks the maximum value encountered. After processing the entire level, it appends the maximum to the result list. This approach is both intuitive and efficient, avoiding extra data structures for level grouping.

Optimal Approach

Use a queue initialized with the root node. While the queue is not empty, determine the number of nodes at the current level (queue size). Iterate exactly that many times, popping nodes from the queue, updating the maximum value for the level, and enqueueing their children if present. Append the maximum value after processing each level. Return the list of maximums after the traversal completes.

Time

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.

Solution

1class Solution:
  def largestValues(self, root: Optional[TreeNode]) -> List[int]:
      if not root:
          return []
      
      res = []
      q = deque([root])
      
      while q:
          level_size = len(q)
          level_max = float("-inf")
          
          for _ in range(level_size):
              node = q.popleft()
              level_max = max(level_max, node.val)
              
              if node.left:
                  q.append(node.left)
              if node.right:
                  q.append(node.right)
          
          res.append(level_max)
      
      return res

Step-by-Step Solution

1

Return Empty List for Null Root to Handle Edge Case

3if 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.

2

Initialize Result List and Queue with Root Node

6res = []
7q = deque([root])

Objective

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.

Key Insight

The result list accumulates the largest values per level, while the queue maintains the frontier of nodes to process. Initializing the queue with the root sets the BFS in motion, ensuring the traversal starts from the top of the tree.

Interview Quick-Check

Core Logic

The queue holds nodes to be processed level by level, enabling BFS traversal.

State & Boundaries

The result list is empty initially and grows by one element per tree level.

3

Process Each Level by Iterating Over Current Queue Size

9while q:
  level_size = len(q)
  level_max = float("-inf")
  for _ in range(level_size):
      node = q.popleft()

Objective

To traverse the tree level by level by iterating exactly over the number of nodes currently in the queue, which represents one level.

Key Insight

By capturing the queue size at the start of each iteration, the algorithm isolates nodes belonging to the current level. This allows processing all nodes of a level before moving on to the next, preserving the BFS level-order property and enabling accurate aggregation of maximum values per level.

Interview Quick-Check

Core Logic

Iterating over the queue size ensures all nodes of the current level are processed before children are enqueued.

State & Boundaries

The while loop continues until all levels are processed and the queue is empty.

Common Pitfalls & Bugs

Setting level_max to 0 or failing to reset it each level leads to wrong answers, especially when levels contain negative values.

4

Track Maximum Value per Level and Enqueue Children

15level_max = max(level_max, node.val)
17if node.left:
18    q.append(node.left)
19if node.right:
20    q.append(node.right)

Objective

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.

Key Insight

Updating the maximum value during the level iteration captures the largest node value at that depth. Enqueuing children prepares the queue for the next level, maintaining the BFS traversal order. This step ensures that the algorithm correctly aggregates per-level maximums while progressing through the tree.

Interview Quick-Check

Core Logic

Updating level_max with max(level_max, node.val) tracks the largest value at the current level.

State & Boundaries

Only non-null children are enqueued to avoid processing invalid nodes.

Common Pitfalls & Bugs

Forgetting to enqueue children or incorrectly updating level_max can lead to incorrect results.

5

Append Level Maximum to Result After Processing Each Level

22	`res.append(level_max)`

Objective

To record the largest value found at the current level into the result list after all nodes of that level have been processed.

Key Insight

Appending the maximum after processing the entire level ensures that the result accurately reflects the largest node value at that depth. This step finalizes the aggregation for the current level before moving on to the next.

Interview Quick-Check

Core Logic

Appending level_max after the for loop captures the maximum value for the entire level.

6

Return the List of Largest Values per Level

24	`return res`

Objective

To return the final list containing the largest values found at each level of the tree after BFS traversal completes.

Key Insight

Returning the accumulated result list provides the solution to the problem as specified. The list length corresponds to the number of levels in the tree, and each element is the maximum value found at that level.

Interview Quick-Check

Core Logic

Returning res provides the final answer after all levels have been processed.

Line Analysis

This solution has 3 Critical lines interviewers watch for.

Line 3 Critical

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.

Line 4 Critical

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.

Line 15 Critical

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.

Line 7 Core

q = deque([root])

Initialize the queue with the root node to start BFS.

The queue maintains the frontier of nodes to process, starting with the root to begin level-order traversal.

Line 10 Core

level_size = len(q)

Determine the number of nodes at the current level.

Capturing the queue size at the start of the loop isolates nodes belonging to the current level, enabling level-wise processing.

Line 14 Core

node = q.popleft()

Remove the next node from the queue for processing.

Dequeuing nodes in FIFO order ensures BFS visits nodes level by level.

Line 18 Core

q.append(node.left)

Add the left child to the queue for next level processing.

Enqueuing the left child extends the BFS frontier to the next level, enabling complete traversal.

Line 20 Core

q.append(node.right)

Add the right child to the queue for next level processing.

Enqueuing the right child maintains BFS traversal completeness by including all nodes.

Line 22 Core

res.append(level_max)

Append the largest value found at the current level to the result list.

This step finalizes the aggregation for the current level, ensuring the result reflects the problem's requirement.

Line 11 Core

level_max = float("-inf")

Initialize the maximum value for the current level to negative infinity.

Starting with negative infinity ensures any node value at this level will update the maximum correctly.

Line 13 Core

for _ in range(level_size):

Iterate exactly over the nodes at the current level.

This for loop processes all nodes of the current level before moving on to the next, preserving BFS level boundaries.

Line 24 Core

return res

Return the list of largest values per level after traversal completes.

Returning the accumulated results provides the final solution as specified by the problem.

Line 9 Standard

while q:

Continue processing while there are nodes in the queue.

The while loop ensures BFS continues until all nodes have been visited and processed level by level.

Line 17 Standard

if node.left:

Check if the current node has a left child.

This conditional ensures only valid child nodes are enqueued for future processing, maintaining correctness.

Line 19 Standard

if node.right:

Check if the current node has a right child.

This conditional ensures only valid child nodes are enqueued, preventing errors.

Line 6 Standard

res = []

Initialize the result list to store largest values per level.

This list accumulates the maximum values found at each level during BFS traversal.

Test Your Understanding

Why does iterating over the queue size at each step correctly isolate nodes belonging to the same tree level?

Because the queue initially contains all nodes at the current level, and by iterating exactly that many times, the algorithm processes all nodes of that level before enqueuing their children, which belong to the next level. This preserves the level boundaries in the BFS traversal.

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

or drill a free problem

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`

9	`while q:`
10	`level_size = len(q)`
11	`level_max = float("-inf")`
13	`for _ in range(level_size):`
14	`node = q.popleft()`

Problem

Example

Approach

Solution

Step-by-Step Solution

Return Empty List for Null Root to Handle Edge Case

Initialize Result List and Queue with Root Node

Process Each Level by Iterating Over Current Queue Size

Track Maximum Value per Level and Enqueue Children

Append Level Maximum to Result After Processing Each Level

Return the List of Largest Values per Level

Line Analysis

Test Your Understanding

Related Problems

Don't just read it. Drill it.