Find Largest Value in Each Tree Row
The key idea
Each tree row is exactly one BFS level. Process the queue one full level at a time and keep the maximum value seen in that level; one breadth-first sweep yields every row's largest value in order.
Problem
Given the root of a binary tree, return an array of the largest value in each row of the tree, ordered from the top row (the root) down to the bottom.
Each row is one level of the tree: the root is row 0, its children are row 1, and so on. For every row you must report the single greatest node value found on that level. If the tree is empty (root is null), return an empty array.
Constraints
- The number of nodes in the tree is in the range
[0, 10^4]. -2^31 <= Node.val <= 2^31 - 1
Examples
Input: root = [1,3,2,5,3,null,9]
Output: [1,3,9]
Input: root = [1,2,3]
Output: [1,3]
Input: root = []
Output: []
Complexity
Time: O(n) Space: O(n)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More BFS / DFS problems
- 01 MatrixMEDIUM
- Average of Levels in Binary TreeEASY
- Binary Tree Level Order TraversalMEDIUM
- Binary Tree Level Order Traversal IIMEDIUM
- Binary Tree Right Side ViewMEDIUM
- Binary Tree Zigzag Level Order TraversalMEDIUM
- Find Bottom Left Tree ValueMEDIUM
- Flood FillEASY
- Keys and RoomsMEDIUM
- Max Area of IslandMEDIUM
- Maximum Level Sum of a Binary TreeMEDIUM
- Minimum Depth of Binary TreeEASY