Find Largest Value in Each Tree Row
Medium · Trees · Tree · Breadth-First Search · Binary Tree
Problem
Given the root of a binary tree, return a list with the largest value in each row of the tree, from the top row down.
An empty tree has no rows, so its answer is an empty list.
Examples
Input: root = [4,9,2,1,null,7,5] Output: [4,9,7]
The rows are [4], [9, 2] and [1, 7, 5]; their largest values are 4, 9 and 7.
Input: root = [] Output: []
An empty tree has no rows.
Constraints
- The number of nodes is in the range [0, 10^4]
- -2^31 <= Node.val <= 2^31 - 1
Approaches
- Find the height, then walk once per row — time O(n · h), space O(h)
Follow-up
What if the tree were too tall for a queue of a whole row to be the bottleneck, but very deep? A depth-first walk carrying the depth uses memory proportional to the height instead of the widest row; written with an explicit stack it also avoids recursion limits.
Related problems
Start free on Cariara · Coding problems · System design studio
