Problem Description

You are given the root of a binary tree. Your task is to find the largest value in each row (level) of the tree and return these values as an array.

The tree is 0-indexed, meaning the root is at level 0, its children are at level 1, and so on.

For example, if you have a binary tree like this:

      1
     / \
    3   2
   / \   \
  5   3   9

The largest values at each level would be:

• Level 0: 1 (only one node)
• Level 1: 3 (between 3 and 2)
• Level 2: 9 (between 5, 3, and 9)

So the output would be [1, 3, 9].

The solution uses a Breadth-First Search (BFS) approach with a queue. Starting from the root, it processes all nodes at each level before moving to the next level. For each level, it tracks the maximum value among all nodes at that level. The algorithm works by:

1. Starting with the root node in a queue
2. For each level, processing all nodes currently in the queue
3. Finding the maximum value among these nodes using max(x, node.val) where x starts at negative infinity
4. Adding all children of the current level's nodes to the queue for the next iteration
5. Appending the maximum value found to the result array
6. Repeating until the queue is empty (all levels processed)

If the tree is empty (root is None), the function returns an empty array.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: A binary tree is a special type of graph with nodes (TreeNodes) and edges (parent-child relationships).

Is it a tree?

• Yes: The problem explicitly states we're working with a binary tree structure where each node has at most two children and there are no cycles.

DFS

• Yes: We arrive at DFS as a suitable approach for this tree problem.

Conclusion: The flowchart suggests using DFS (Depth-First Search) for this tree traversal problem.

While the provided solution uses BFS (level-order traversal with a queue), DFS is equally valid for finding the largest value in each row. With DFS, we would:

1. Track the current depth/level as we traverse
2. Maintain a list where index corresponds to the tree level
3. Update the maximum value at each level as we visit nodes
4. Use recursion to traverse left and right subtrees, incrementing the depth

Here's how DFS would work:

def largestValues(self, root: Optional[TreeNode]) -> List[int]:
    ans = []
  
    def dfs(node, depth):
        if not node:
            return
      
        if depth == len(ans):
            ans.append(node.val)
        else:
            ans[depth] = max(ans[depth], node.val)
      
        dfs(node.left, depth + 1)
        dfs(node.right, depth + 1)
  
    dfs(root, 0)
    return ans

Both DFS and BFS are valid approaches for this level-based tree problem, with BFS being more intuitive for level-order operations and DFS being a natural tree traversal pattern.

Intuition

When we need to find the largest value in each row of a tree, we're essentially looking at a level-by-level analysis problem. The key insight is that we need to process all nodes at the same depth together to compare their values.

Think of the tree as floors in a building - we want to find the maximum value on each floor. To do this systematically, we have two main approaches:

Why BFS feels natural here: Since we're looking for row-wise (level-wise) maximum values, it makes sense to process the tree level by level. BFS naturally groups nodes by their level - we process all nodes at depth 0, then all nodes at depth 1, and so on. This grouping aligns perfectly with our goal of finding the maximum value per level.

With BFS, we use a queue to maintain all nodes at the current level. Before moving to the next level, we:

1. Count how many nodes are at the current level (len(q))
2. Process exactly that many nodes, tracking their maximum value
3. While processing, add their children to the queue for the next level

The initialization of x = -inf ensures that even negative values in the tree are handled correctly, as any actual node value will be greater than negative infinity.

Why DFS also works: Although less intuitive for level-order problems, DFS can solve this by tracking the depth as we traverse. As we visit each node, we know its depth in the tree. We can maintain an array where ans[i] stores the maximum value seen so far at depth i. Each time we visit a node at depth d, we either:

• Initialize ans[d] if this is the first node we've seen at this depth
• Update ans[d] if the current node's value is larger

The beauty of both approaches is that they guarantee we visit every node exactly once, making the time complexity O(n) where n is the number of nodes. The BFS approach just happens to group nodes more naturally for this particular problem.

Learn more about Tree, Depth-First Search, Breadth-First Search and Binary Tree patterns.

Solution Approach

The reference solution uses BFS (Breadth-First Search) to traverse the tree level by level. Let's walk through the implementation step by step:

Data Structures Used:

• deque: A double-ended queue for efficient O(1) operations when adding/removing from both ends
• ans: A list to store the maximum value found at each level

Algorithm Implementation:

1. Handle Edge Case: First, we check if the root is None. If the tree is empty, we return an empty list immediately.

2. Initialize BFS: We create a queue q using deque([root]) and start with the root node in it. The deque allows us to efficiently popleft() and append() nodes.

3. Level-by-Level Processing: The outer while q: loop continues as long as there are nodes to process. Each iteration of this loop represents processing one complete level of the tree.

4. Track Maximum per Level: For each level, we:

   • Initialize x = -inf to track the maximum value at this level. Using negative infinity ensures any actual node value will be larger.
   • Use for _ in range(len(q)): to process exactly the number of nodes that were in the queue at the start of this level. This is crucial - len(q) is evaluated once before the loop starts, giving us the exact count of nodes at the current level.

5. Process Each Node: Within the inner loop:

   • Remove a node from the front of the queue with node = q.popleft()
   • Update the maximum value: x = max(x, node.val)
   • Add the node's children to the queue for the next level:

     if node.left:
         q.append(node.left)
     if node.right:
         q.append(node.right)

6. Store Level Maximum: After processing all nodes at the current level, append the maximum value found to our result: ans.append(x)

Why This Works:

• The queue maintains a clear separation between levels. When we start processing a level, the queue contains only nodes from that level.
• As we process these nodes, we add their children (next level nodes) to the back of the queue.
• The range(len(q)) ensures we process exactly the nodes from the current level before moving to the next.

Time Complexity: O(n) where n is the number of nodes, as we visit each node exactly once.

Space Complexity: O(w) where w is the maximum width of the tree, which is the maximum number of nodes at any level. In the worst case (a complete binary tree), this could be O(n/2) = O(n).

Example Walkthrough

Let's walk through the BFS solution with this example tree:

      1
     / \
    3   2
   / \   \
  5   3   9

Initial Setup:

• root = 1, which is not None, so we proceed
• Create q = deque([1]) (queue contains just the root)
• Initialize ans = []

Level 0 Processing:

• Queue state: [1]
• len(q) = 1, so we'll process 1 node
• Initialize x = -inf
• Process node 1:
  • node = q.popleft() → node = 1
  • x = max(-inf, 1) → x = 1
  • Add children: q.append(3), q.append(2)
  • Queue now: [3, 2]
• Append x to ans: ans = [1]

Level 1 Processing:

• Queue state: [3, 2]
• len(q) = 2, so we'll process 2 nodes
• Initialize x = -inf
• Process node 3:
  • node = q.popleft() → node = 3
  • x = max(-inf, 3) → x = 3
  • Add children: q.append(5), q.append(3)
  • Queue now: [2, 5, 3]
• Process node 2:
  • node = q.popleft() → node = 2
  • x = max(3, 2) → x = 3 (stays 3)
  • Add children: no left child, q.append(9)
  • Queue now: [5, 3, 9]
• Append x to ans: ans = [1, 3]

Level 2 Processing:

• Queue state: [5, 3, 9]
• len(q) = 3, so we'll process 3 nodes
• Initialize x = -inf
• Process node 5:
  • node = q.popleft() → node = 5
  • x = max(-inf, 5) → x = 5
  • No children to add
  • Queue now: [3, 9]
• Process node 3:
  • node = q.popleft() → node = 3
  • x = max(5, 3) → x = 5
  • No children to add
  • Queue now: [9]
• Process node 9:
  • node = q.popleft() → node = 9
  • x = max(5, 9) → x = 9
  • No children to add
  • Queue now: []
• Append x to ans: ans = [1, 3, 9]

Final Step:

• Queue is empty, exit while loop
• Return ans = [1, 3, 9]

The key insight is that len(q) captures the exact number of nodes at each level before we start processing, ensuring we handle all nodes at one level before moving to the next.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the number of nodes in the binary tree.

The algorithm uses BFS (Breadth-First Search) to traverse the tree level by level. Each node in the tree is visited exactly once - it's added to the queue once and processed once when it's dequeued. For each node, we perform constant time operations: comparing values with max(), checking for left/right children, and adding children to the queue. Since we visit all n nodes exactly once and perform O(1) operations for each node, the total time complexity is O(n).

Space Complexity: O(n), where n is the number of nodes in the binary tree.

The space complexity is determined by two factors:

1. Queue space: In the worst case, the queue stores all nodes at the widest level of the tree. For a complete binary tree, the last level can contain up to n/2 nodes, making the queue space O(n).
2. Output list: The ans list stores one value per level. In the worst case (a skewed tree), there could be n levels, but typically it's O(log n) for a balanced tree. However, since the queue dominates the space usage with O(n) in the worst case, the overall space complexity remains O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Not Preserving Level Boundaries

One of the most common mistakes is failing to properly track which nodes belong to the current level versus the next level. If you don't capture len(queue) before the inner loop starts, you'll end up processing nodes from multiple levels together.

Incorrect approach:

while queue:
    level_max = -inf
    # WRONG: This will process ALL nodes, not just current level
    while queue:
        node = queue.popleft()
        level_max = max(level_max, node.val)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    result.append(level_max)

Correct approach:

while queue:
    level_max = -inf
    level_size = len(queue)  # Capture current level size
    for _ in range(level_size):  # Process exactly this many nodes
        node = queue.popleft()
        level_max = max(level_max, node.val)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    result.append(level_max)

2. Incorrect Initialization of Maximum Value

Using 0 or a small positive number as the initial maximum value can fail when all nodes in a level have negative values.

Incorrect:

level_max = 0  # WRONG: What if all values in level are negative?

Correct:

level_max = -inf  # Handles any possible node value
# Alternative: Use the first node's value
level_max = queue[0].val  # Then start loop from index 1

3. Using Regular List Instead of Deque

While a regular Python list works functionally, using list.pop(0) has O(n) time complexity, making the overall algorithm O(n²) instead of O(n).

Inefficient:

queue = [root]
while queue:
    node = queue.pop(0)  # O(n) operation

Efficient:

from collections import deque
queue = deque([root])
while queue:
    node = queue.popleft()  # O(1) operation

4. Not Handling Edge Cases Properly

Forgetting to check for an empty tree or assuming the tree has at least one node.

Incorrect:

def largestValues(self, root):
    result = []
    queue = deque([root])  # Will add None to queue if root is None
    while queue:
        # Processing None will cause AttributeError

Correct:

def largestValues(self, root):
    if not root:
        return []
    result = []
    queue = deque([root])

5. Modifying Queue Length During Iteration

Some developers try to check len(queue) dynamically within the loop, which changes as nodes are added.

Incorrect:

i = 0
while i < len(queue):  # len(queue) changes as we add children!
    node = queue.popleft()
    # ... add children to queue
    i += 1

Correct:

level_size = len(queue)  # Capture once before loop
for _ in range(level_size):  # Fixed iteration count
    node = queue.popleft()
    # ... add children to queue