Find Largest Value in Each Tree Row — Problem & Solution
Find Largest Value in Each Tree Row solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Find Largest Value in Each Tree Row is a medium coding problem on depth-first search, breadth-first search and trees, asked in Amazon, Meta and LinkedIn interviews.
- Difficulty: Medium
- Topics: Depth-First Search, Breadth-First Search, Trees
- Asked at: Amazon, Meta, LinkedIn
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given the root of a binary tree, return an array whose i-th element is the largest value in row i of the tree (row 0 holds the root, row 1 its children, and so on).
Example 1
Input: root = [1,3,2,5,3,null,9]
Output: [1,3,9]
Explanation: Row by row: {1}, {3, 2}, {5, 3, 9}. The largest of each is 1, 3 and 9.
Example 2
Input: root = [1,2,3]
Output: [1,3]
Explanation: The second row holds 2 and 3.
Example 3
Input: root = []
Output: []
Explanation: An empty tree has no rows.
Constraints
The number of nodes in the tree is in the range [0, 10^4]-2^31 <= Node.val <= 2^31 - 1
Hints for Find Largest Value in Each Tree Row
Hint 1
You need to know which nodes share a row — a breadth-first walk hands them to you one row at a time.
Hint 2
Process the queue in batches: the queue's size at the start of a batch is exactly the number of nodes in that row.
Hint 3
Start each row's maximum from its first node rather than from a sentinel — the values reach the full 32-bit range.
How to solve Find Largest Value in Each Tree Row
Level-order traversal groups the nodes by row. Scanning each row while it is dequeued and keeping its maximum gives the answer in one pass.
Approach
- If the tree is empty, return an empty array.
- Put the root in a queue. While the queue is not empty, let
sizebe its length. - Dequeue
sizenodes, tracking the largest value among them and enqueuing their children. - Append that row's largest value to the answer.
Why it works
At the start of each batch the queue holds exactly the nodes of one row — the previous batch enqueued precisely the children of the row before — so each batch's maximum is that row's maximum.
Complexity
- Time —
O(n) - Space —
O(w), the widest row — O(n) at worst
Pitfalls
- Values can be -2^31; starting a row's maximum at 0 or at -1 gives wrong answers on all-negative rows.
- Read the row size before the loop that dequeues it; the queue grows while the row is processed.
- An empty tree returns an empty array.
Reference solution
Python
from typing import List, Optional
def largestValues(root: Optional[TreeNode]) -> List[int]:
out = []
level = [root] if root is not None else []
while level:
best = level[0].val
nxt = []
for node in level:
if node.val > best:
best = node.val
if node.left is not None:
nxt.append(node.left)
if node.right is not None:
nxt.append(node.right)
out.append(best)
level = nxt
return outJava
public static int[] largestValues(TreeNode root) {
List<Integer> out = new ArrayList<>();
ArrayDeque<TreeNode> queue = new ArrayDeque<>();
if (root != null) queue.add(root);
while (!queue.isEmpty()) {
int size = queue.size();
int best = queue.peek().val;
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
best = Math.max(best, node.val);
if (node.left != null) queue.add(node.left);
if (node.right != null) queue.add(node.right);
}
out.add(best);
}
int[] res = new int[out.size()];
for (int i = 0; i < res.length; i++) res[i] = out.get(i);
return res;
}C++
vector<int> largestValues(TreeNode* root) {
vector<int> out;
queue<TreeNode*> q;
if (root) q.push(root);
while (!q.empty()) {
int size = (int) q.size();
int best = q.front()->val;
for (int i = 0; i < size; i++) {
TreeNode* node = q.front();
q.pop();
best = max(best, node->val);
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
out.push_back(best);
}
return out;
}JavaScript
var largestValues = function(root) {
var out = [];
var level = root === null ? [] : [root];
while (level.length > 0) {
var best = level[0].val, next = [];
for (var i = 0; i < level.length; i++) {
var node = level[i];
if (node.val > best) best = node.val;
if (node.left !== null) next.push(node.left);
if (node.right !== null) next.push(node.right);
}
out.push(best);
level = next;
}
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Breadth-First Search (BFS)