515. Find Largest Value in Each Tree Row
Model: qwen3.5:9b
Topics: Tree,Depth-first Search,Breadth-first Search
FAANG asked: 1
Acceptance rate: 62.4%
Problem Breakdown
We need to traverse a binary tree and extract the maximum value present at each depth level (row), returning these as an array indexed by row number starting from 0.
Inputs:
root: The root node of a Binary Tree (TreeNode). Can beNone.
Outputs:
- A list of integers, where index
icorresponds to the maximum value found at depthi.
Constraints & Edge Cases:
- Empty Input: If
rootisNone, return an empty array immediately. - Negative Values: Node values can be negative (down to
-2^31). We cannot initialize our running max with 0 or a small positive integer; we must handle the first node of each level carefully. - Tree Shape: The tree could be skewed (all left children) or balanced. BFS handles both uniformly without special logic for skewness.
Intuition
The problem explicitly asks us to group nodes by their “row” or depth in a binary tree. This structure strongly suggests a Breadth-First Search (BFS).
A Depth-First Search (DFS) approach is possible if we maintain an array indexed by height and update the max at each step, but it requires tracking recursion depth explicitly. BFS naturally processes nodes level-by-level using a queue.
Why not DFS? While DFS works with time complexity, managing state for “current row” in recursive calls adds overhead or global variables that can be messy to reason about during an interview.
Key Insight: If we use a standard BFS queue:
- We know exactly how many nodes belong to the current level by checking
len(queue)at the start of each outer loop iteration. - As we pop these specific number of nodes, we update our running maximum for that row.
- Any children pushed into the queue will automatically be processed in the next outer loop iteration (next row).
This allows us to aggregate results per level without needing a separate depth counter or recursion stack.
Approach
- Initialization: Create an empty list
resultand import/initialize a deque for our BFS queue. If root is null, return[]. Push the root into the queue. - Level Processing Loop: While the queue has nodes:
- Determine the number of nodes currently in the queue (
level_size). This defines the boundary between rows. - Initialize
max_valfor this row. A safe way is to set it on the first node processed or use a sentinel like-float('inf'). Given constraints, using the value of the first popped node as initial max avoids magic numbers. - Inner Loop: Iterate exactly
level_sizetimes:- Pop left from queue (
node). - Update
max_val = max(max_val, node.val). - If
node.left, append to queue. - If
node.right, append to queue.
- Pop left from queue (
- Append the finalized
max_valfor this row intoresult.
- Determine the number of nodes currently in the queue (
- Return: Return
result.
Complexity Analysis
- Time Complexity: , where is the number of nodes in the tree. We visit every node exactly once (pushed and popped from queue).
- Space Complexity: , where is the maximum width of the binary tree (the largest level size) for the queue storage at any given time. In a balanced tree this is roughly , in worst case skewed it’s 1. The output array takes space ( height), which is negligible compared to queue usage in wide trees, but technically part of return value allocation.
Solution
from collections import deque
from typing import Optional, List
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def largestValues(root: Optional[TreeNode]) -> List[int]:
if not root:
return []
queue = deque([root])
result = []
while queue:
level_size = len(queue)
current_max = -float('inf') # Initialize with negative infinity
for _ in range(level_size):
node = queue.popleft()
if node.val > current_max:
current_max = node.val
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(current_max)
return result
Edge Cases Handled
- Empty Tree (
rootis None): The function checksif not rootat the start and returns an empty list immediately. - Single Node: The loop runs once, processes one node, sets max to that value, appends it, then queue empties. Returns
[val]. - Negative Values: Initializing
current_max = -float('inf')ensures any valid integer (even negative ones) will update the maximum correctly on the first iteration of a level’s inner loop. - Skewed Trees: The logic relies only on node existence, not tree balance; skewed trees simply result in fewer nodes per row or single-node rows processed sequentially.