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.

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