LeetCode 515 - Find Largest Value in Each Tree Row
The problem asks us to find the largest value in each row of a binary tree, where a row is defined as all nodes at the same depth. The input is the root of a binary tree, which may contain up to 10,000 nodes, and each node's value is a signed 32-bit integer.
Difficulty: 🟡 Medium
Topics: Tree, Depth-First Search, Breadth-First Search, Binary Tree
Solution
Problem Understanding
The problem asks us to find the largest value in each row of a binary tree, where a row is defined as all nodes at the same depth. The input is the root of a binary tree, which may contain up to 10,000 nodes, and each node's value is a signed 32-bit integer. The output should be a list of integers, where the first element corresponds to the largest value in the root level (depth 0), the second element corresponds to the largest value in the first level (depth 1), and so on.
The problem guarantees that the tree is well-formed and may be empty. Important edge cases include an empty tree, a tree with only one node, and a tree where all values are negative or the same. These scenarios can easily break naive implementations if not handled explicitly.
The main challenge is to traverse the tree level by level, keeping track of the maximum value for each level, while respecting time and space efficiency for large trees.
Approaches
A brute-force approach would be to traverse the tree multiple times, once for each level, and compute the maximum for that level. This guarantees correctness because it explicitly examines all nodes at each depth. However, this is inefficient because each traversal repeats work already done in previous levels, leading to O(n^2) time in the worst case for unbalanced trees.
The optimal approach uses either Breadth-First Search (BFS) or Depth-First Search (DFS) to visit each node exactly once while maintaining the maximum value for the current depth. BFS is natural here because it processes nodes level by level. We use a queue to iterate through nodes in the current level, track the maximum, and append it to the result. DFS is also possible by passing the current depth in recursive calls and updating the maximum for each level.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n^2) | O(n) | Multiple traversals per level, very inefficient for large trees |
| Optimal (BFS/DFS) | O(n) | O(w) | Single traversal of all nodes, space depends on max width of tree |
Algorithm Walkthrough
- Check if the root is
None. If so, return an empty list since the tree has no nodes. - Initialize an empty list
resultto store the maximum values for each row. - Initialize a queue and add the root node. This queue will track nodes to process level by level.
- While the queue is not empty, determine the number of nodes at the current level by measuring the queue's length. This ensures we only process nodes in the current row.
- Initialize a variable
level_maxto negative infinity. This will track the maximum value in the current row. - Iterate over all nodes in the current level. For each node, update
level_maxif the node's value is greater. - If the node has a left child, enqueue it. If the node has a right child, enqueue it. This ensures the next level is prepared for processing.
- After processing all nodes in the current level, append
level_maxtoresult. - Repeat steps 4-8 until all levels are processed.
- Return
result.
Why it works: Each node is visited exactly once, and the maximum value for each row is computed before moving to the next row. BFS guarantees that nodes are processed level by level, preserving the correct ordering of maximum values in result.
Python Solution
# 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
from typing import List, Optional
from collections import deque
class Solution:
def largestValues(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
result = []
queue = deque([root])
while queue:
level_size = len(queue)
level_max = float('-inf')
for _ in range(level_size):
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)
return result
This Python implementation mirrors the algorithm steps exactly. We check for an empty tree, initialize the result list and queue, and process the tree level by level. The level_max variable tracks the maximum value per row, and the BFS ensures correct row ordering.
Go Solution
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func largestValues(root *TreeNode) []int {
if root == nil {
return []int{}
}
result := []int{}
queue := []*TreeNode{root}
for len(queue) > 0 {
levelSize := len(queue)
levelMax := -1 << 31 // equivalent to negative infinity for 32-bit int
for i := 0; i < levelSize; i++ {
node := queue[0]
queue = queue[1:]
if node.Val > levelMax {
levelMax = node.Val
}
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
}
result = append(result, levelMax)
}
return result
}
In Go, we handle nil nodes explicitly and use slices as queues. The levelMax variable is initialized to the minimum 32-bit integer value, mirroring Python's float('-inf'). Slice operations simulate queue behavior efficiently for BFS.
Worked Examples
Example 1: root = [1,3,2,5,3,null,9]
Processing steps:
| Level | Nodes | level_max | Queue after level |
|---|---|---|---|
| 0 | [1] | 1 | [3, 2] |
| 1 | [3, 2] | 3 | [5, 3, 9] |
| 2 | [5, 3, 9] | 9 | [] |
Output: [1, 3, 9]
Example 2: root = [1,2,3]
Processing steps:
| Level | Nodes | level_max | Queue after level |
|---|---|---|---|
| 0 | [1] | 1 | [2, 3] |
| 1 | [2, 3] | 3 | [] |
Output: [1, 3]
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n) | Each node is visited exactly once, where n is the total number of nodes |
| Space | O(w) | BFS queue stores at most the maximum number of nodes at any level, w is the tree width |
The linear time complexity is optimal because we must examine every node at least once. Space complexity depends on the breadth of the tree; in a balanced tree, this is roughly O(n/2), and in a skewed tree, O(1) for DFS.
Test Cases
# Provided examples
assert Solution().largestValues(None) == [] # empty tree
assert Solution().largestValues(TreeNode(1)) == [1] # single node
assert Solution().largestValues(TreeNode(1, TreeNode(3), TreeNode(2, None, TreeNode(9)))) == [1, 3, 9]
assert Solution().largestValues(TreeNode(1, TreeNode(2), TreeNode(3))) == [1, 3]
# All negative values
assert Solution().largestValues(TreeNode(-1, TreeNode(-2), TreeNode(-3))) == [-1, -2]
# Unbalanced tree
assert Solution().largestValues(TreeNode(1, TreeNode(2, TreeNode(4), None), TreeNode(3))) == [1, 3, 4]
# Tree with duplicate values
assert Solution().largestValues(TreeNode(2, TreeNode(2), TreeNode(2))) == [2, 2]
| Test | Why |
|---|---|
| Empty tree | Checks that edge case returns empty list |
| Single node | Ensures trivial tree handled correctly |
| Mixed tree | Validates BFS captures row maxima accurately |
| All negative | Ensures negative numbers are correctly compared |
| Unbalanced tree | Tests correctness on uneven depths |
| Duplicate values | Ensures equality does not break maximum tracking |
Edge Cases
One important edge case is an empty tree. A naive implementation might attempt to access root.val without checking for None, which would cause a runtime error. We explicitly handle this case at the beginning by returning an empty list.
A second edge case is a tree with all negative values. Using a naive level_max = 0 initialization would incorrectly produce 0 as the maximum. We avoid this by initializing level_max to negative infinity (float('-inf') in Python, -1 << 31 in Go), ensuring all negative values are correctly compared.
A third edge case is an unbalanced tree, where some levels have far fewer nodes than others.