Given the root of a binary tree, return an array of the largest value in each row of the tree (0-indexed).
Example 1:
Input: root = [1,3,2,5,3,null,9] Output: [1,3,9]
Example 2:
Input: root = [1,2,3] Output: [1,3]
Constraints:
[0, 104].-231 <= Node.val <= 231 - 1Problem Overview: Given the root of a binary tree, return the maximum value found at each depth level. Each row of the tree represents a level, and you need the largest node value from that level before moving to the next.
Approach 1: Breadth-First Search (Level Order Traversal) (Time: O(n), Space: O(w))
The most direct way is a level-order traversal using a queue. Start from the root and process nodes level by level using Breadth-First Search. For each level, iterate through all nodes currently in the queue, track the maximum value seen, and append it to the result list. While processing a node, push its left and right children into the queue so the next iteration processes the next row.
The key insight: BFS naturally groups nodes by depth. Since each queue cycle processes exactly one tree level, calculating the maximum value for that row becomes straightforward. Every node is visited once, giving O(n) time complexity. The queue can hold up to the maximum width of the tree, so space complexity is O(w). This approach is intuitive and commonly expected when solving level-based problems on a binary tree using Breadth-First Search.
Approach 2: Depth-First Search with Level Tracking (Time: O(n), Space: O(h))
A recursive Depth-First Search also works if you track the depth of each node. Traverse the tree using preorder traversal (node, left, right) and maintain a list where index i stores the maximum value for level i. When visiting a node, check if this is the first time reaching that depth. If so, append the value. Otherwise, update the stored value with max(current, node.val).
The key idea: DFS reaches nodes in depth order, and the recursion stack implicitly tracks levels. Instead of processing nodes level by level, you update the result as you discover nodes. Each node contributes exactly once, so time complexity remains O(n). The recursion stack depth is bounded by the height of the tree, giving O(h) space. This technique is useful when you prefer recursion or when solving related problems involving Depth-First Search and depth tracking.
Recommended for interviews: The BFS level-order traversal is usually the first approach interviewers expect because the problem explicitly asks for the largest value per row. BFS directly mirrors that structure and is easier to reason about under pressure. The DFS solution demonstrates deeper understanding of tree traversal patterns and shows that you can convert level-based problems into depth-indexed computations.
The BFS approach involves traversing the tree level by level and keeping track of the largest value at each level. We employ a queue data structure to facilitate level-wise traversal and maintain a list to store the maximum values for each row.
This solution uses a queue to perform a BFS traversal on the binary tree. Each level is processed entirely before moving to the next, and the largest value encountered at each level is recorded in the result array. The function returns the array of largest values and updates the size of the returned array via the pointer returnSize.
Time Complexity: O(n) where n is the number of nodes in the tree, since each node is processed exactly once. Space Complexity: O(n) due to the storage required to keep the queue and the result array.
The DFS approach involves recursively exploring each branch of the tree depth-first and leveraging the depth of recursion to determine the level of the tree. For each level not yet considered, the maximum value is initialized, or updated if a new larger value is found.
This C++ solution employs a depth-first search (DFS) paradigm using recursion. We track the depth to associate the maximum value found at each level. If a given depth isn’t present in the list of maximum values, it initializes it; otherwise, it updates the level’s maximum with the current node’s value if it exceeds the current maximum.
Time Complexity: O(n) where n is the number of nodes in the tree, since every node is visited once. Space Complexity: O(h) where h is the height of the tree due to recursion stack.
| Approach | Complexity |
|---|---|
| Breadth-First Search (BFS) Approach | Time Complexity: O(n) where n is the number of nodes in the tree, since each node is processed exactly once. Space Complexity: O(n) due to the storage required to keep the queue and the result array. |
| Depth-First Search (DFS) Approach | Time Complexity: O(n) where n is the number of nodes in the tree, since every node is visited once. Space Complexity: O(h) where h is the height of the tree due to recursion stack. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Breadth-First Search (Level Order) | O(n) | O(w) | Best when solving level-based tree problems where results depend on rows or layers |
| Depth-First Search with Level Tracking | O(n) | O(h) | Useful when recursion is preferred or when computing values while traversing depth-first |
Find Largest Value in Tree Row - Leetcode 515 - Python • NeetCodeIO • 11,367 views views
Watch 9 more video solutions →Practice Find Largest Value in Each Tree Row with our built-in code editor and test cases.
Practice on FleetCode