Find Largest Value in Each Tree Row solution and explanation
Google
9 more videos on this problem
LeetCode Find Largest Value In Each Tree Row Explained - JavaNick White · 6:09 · 17K views
Find Largest Value in Tree Row - Leetcode 515 - PythonNeetCodeIO · 8:06 · 11K views
Find Largest Value in Each Tree Row | DFS | BFS | META | Leetcode - 515codestorywithMIK · 22:53 · 7K views
FIND LARGEST VALUE IN EACH TREE ROW | LEETCODE # 515 | PYTHON BFS SOLUTIONCracking FAANG · 6:26 · 1K views
Cracking LeetCode 515 'Largest Value in Each Tree Row' Challenge | Deep Dive with vanAmsenvanAmsen · 9:15 · 508 views
Leetcode 515: Find Largest Value in Each Tree RowAlgorithms Casts · 11:15 · 494 views
Leetcode 515 - Find Largest Value in Each Row (JAVA, Solution Explain!)LC Bear · 6:38 · 280 views
Daily Leetcode #1302: Oct 24, 2023 - 515. Find Largest Value in Each Tree RowProgramming Live with Larry · 4:42 · 210 views
Leetcode 515. Find Largest Value in Each Tree RowJames Lyons · 3:18 · 186 views
515. Find Largest Value in Each Tree RowUdyan is here · 10:18 · 170 views
The problem
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:
- The number of nodes in the tree will be in the range
[0, 104]. -231 <= Node.val <= 231 - 1
Approach overview
Problem 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.
Approach 1: Breadth-First Search (BFS) Approach
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.
from collections import deque
from typing import Optional, List
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def largestValues(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
res = []
q = deque([root])
while q:
level_max = float('-inf')
for _ in range(len(q)):
node = q.popleft()
level_max = max(level_max, node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
res.append(level_max)
return resimport java.util.*;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
class Solution {
public List<Integer> largestValues(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) return result;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int levelMax = Integer.MIN_VALUE;
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
levelMax = Math.max(levelMax, node.val);
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
result.add(levelMax);
}
return result;
}
}#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
vector<int> largestValues(TreeNode* root) {
if (!root) return {};
vector<int> result;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int levelMax = INT_MIN;
int size = q.size();
for (int i = 0; i < size; ++i) {
TreeNode* node = q.front(); q.pop();
levelMax = max(levelMax, node->val);
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
result.push_back(levelMax);
}
return result;
}var largestValues = function(root) {
if (!root) return [];
const result = [];
const queue = [root];
while (queue.length) {
let levelMax = -Infinity;
const levelSize = queue.length;
for (let i = 0; i < levelSize; i++) {
const node = queue.shift();
levelMax = Math.max(levelMax, node.val);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
result.push(levelMax);
}
return result;
};#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
// Definition for a binary tree node.
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
#define MAX_QUEUE_SIZE 10000
struct TreeNode* queue[MAX_QUEUE_SIZE];
int front = 0;
int rear = 0;
void enqueue(struct TreeNode* node) {
if (rear < MAX_QUEUE_SIZE) {
queue[rear++] = node;
}
}
struct TreeNode* dequeue() {
return queue[front++];
}
int* largestValues(struct TreeNode* root, int* returnSize) {
if (!root) {
*returnSize = 0;
return NULL;
}
int* result = (int*)malloc(sizeof(int) * MAX_QUEUE_SIZE);
*returnSize = 0;
front = rear = 0;
enqueue(root);
while (front != rear) {
int levelSize = rear - front;
int levelMax = INT_MIN;
for (int i = 0; i < levelSize; ++i) {
struct TreeNode* node = dequeue();
if (node->val > levelMax) {
levelMax = node->val;
}
if (node->left) {
enqueue(node->left);
}
if (node->right) {
enqueue(node->right);
}
}
result[(*returnSize)++] = levelMax;
}
return result;
}using System;
using System.Collections.Generic;
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
public IList<int> LargestValues(TreeNode root) {
List<int> result = new List<int>();
if (root == null) return result;
Queue<TreeNode> queue = new Queue<TreeNode>();
queue.Enqueue(root);
while (queue.Count > 0) {
int levelMax = Int32.MinValue;
int size = queue.Count;
for (int i = 0; i < size; ++i) {
TreeNode node = queue.Dequeue();
levelMax = Math.Max(levelMax, node.val);
if (node.left != null) queue.Enqueue(node.left);
if (node.right != null) queue.Enqueue(node.right);
}
result.Add(levelMax);
}
return result;
}
}This Python solution uses a deque from the collections module to perform a breadth-first traversal of the tree levels. For each level, it calculates the largest value and appends it to the result list. The use of deque allows efficient removals from the left end.
Time Complexity: O(n), since each node is processed once. Space Complexity: O(n) for storing nodes in the deque and result list.
Approach 2: Depth-First Search (DFS) Approach
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.
from typing import Optional, List
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def largestValues(self, root: Optional[TreeNode]) -> List[int]:
def dfs(node, depth):
if not node:
return
if depth == len(max_values):
max_values.append(node.val)
else:
max_values[depth] = max(max_values[depth], node.val)
dfs(node.left, depth + 1)
dfs(node.right, depth + 1)
max_values = []
dfs(root, 0)
return max_valuesimport java.util.*;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
class Solution {
private void dfs(TreeNode node, int depth, List<Integer> maxValues) {
if (node == null) return;
if (depth == maxValues.size()) {
maxValues.add(node.val);
} else {
maxValues.set(depth, Math.max(maxValues.get(depth), node.val));
}
dfs(node.left, depth + 1, maxValues);
dfs(node.right, depth + 1, maxValues);
}
public List<Integer> largestValues(TreeNode root) {
List<Integer> maxValues = new ArrayList<>();
dfs(root, 0, maxValues);
return maxValues;
}
}#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
void dfs(TreeNode* node, int depth, vector<int>& maxValues) {
if (!node) return;
if (depth == maxValues.size()) {
maxValues.push_back(node->val);
} else {
maxValues[depth] = max(maxValues[depth], node->val);
}
dfs(node->left, depth + 1, maxValues);
dfs(node->right, depth + 1, maxValues);
}
vector<int> largestValues(TreeNode* root) {
vector<int> maxValues;
dfs(root, 0, maxValues);
return maxValues;
}This Python solution leverages a recursive DFS to explore each tree branch. At each depth, it records the highest value; if there’s no entry for the depth, it initializes one with the node’s value. Otherwise, it updates the maximum value for the depth if the current node surpasses it.
Time Complexity: O(n), since each node is visited a single time. Space Complexity: O(h) where h is the height of the tree as the recursion depth may extend to the tree’s height.
Approach 3: BFS
We define a queue q and put the root node into the queue. Each time, we take out all the nodes of the current level from the queue, find the maximum value, and then put all the nodes of the next level into the queue until the queue is empty.
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree.
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function largestValues(root: TreeNode | null): number[] {
const ans: number[] = [];
if (!root) {
return ans;
}
const q: TreeNode[] = [root];
while (q.length) {
const nq: TreeNode[] = [];
let x = -Infinity;
for (const { val, left, right } of q) {
x = Math.max(x, val);
if (left) {
nq.push(left);
}
if (right) {
nq.push(right);
}
}
ans.push(x);
q.length = 0;
q.push(...nq);
}
return ans;
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func largestValues(root *TreeNode) (ans []int) {
if root == nil {
return
}
q := []*TreeNode{root}
for len(q) > 0 {
x := q[0].Val
for i := len(q); i > 0; i-- {
node := q[0]
q = q[1:]
x = max(x, node.Val)
if node.Left != nil {
q = append(q, node.Left)
}
if node.Right != nil {
q = append(q, node.Right)
}
}
ans = append(ans, x)
}
return
}// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std::cell::RefCell;
use std::collections::VecDeque;
use std::rc::Rc;
impl Solution {
pub fn largest_values(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
let mut ans = Vec::new();
let mut q = VecDeque::new();
if root.is_some() {
q.push_back(root.clone());
}
while !q.is_empty() {
let mut x = i32::MIN;
for _ in 0..q.len() {
let node = q.pop_front().unwrap();
let node = node.as_ref().unwrap().borrow();
x = x.max(node.val);
if node.left.is_some() {
q.push_back(node.left.clone());
}
if node.right.is_some() {
q.push_back(node.right.clone());
}
}
ans.push(x);
}
ans
}
}Approach 4: Default Approach
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function largestValues(root: TreeNode | null): number[] {
const res = [];
const dfs = (root: TreeNode | null, depth: number) => {
if (root == null) {
return;
}
const { val, left, right } = root;
if (res.length == depth) {
res.push(val);
} else {
res[depth] = Math.max(res[depth], val);
}
dfs(left, depth + 1);
dfs(right, depth + 1);
};
dfs(root, 0);
return res;
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func largestValues(root *TreeNode) []int {
var ans []int
var dfs func(*TreeNode, int)
dfs = func(root *TreeNode, curr int) {
if root == nil {
return
}
if curr == len(ans) {
ans = append(ans, root.Val)
} else {
ans[curr] = max(ans[curr], root.Val)
}
dfs(root.Left, curr+1)
dfs(root.Right, curr+1)
}
dfs(root, 0)
return ans
}// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
fn dfs(root: &Option<Rc<RefCell<TreeNode>>>, depth: usize, res: &mut Vec<i32>) {
if root.is_none() {
return;
}
let node = root.as_ref().unwrap().borrow();
if res.len() == depth {
res.push(node.val);
} else {
res[depth] = res[depth].max(node.val);
}
Self::dfs(&node.left, depth + 1, res);
Self::dfs(&node.right, depth + 1, res);
}
pub fn largest_values(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
let mut res = Vec::new();
Self::dfs(&root, 0, &mut res);
res
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Breadth-First Search (BFS) Approach | Time Complexity: O(n), since each node is processed once. Space Complexity: O(n) for storing nodes in the deque and result list. |
| Depth-First Search (DFS) Approach | Time Complexity: O(n), since each node is visited a single time. Space Complexity: O(h) where h is the height of the tree as the recursion depth may extend to the tree’s height. |
| BFS | – |
| Default Approach | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Find Largest Value in Each Tree Row easy or hard?
The problem is rated Medium because it requires understanding tree traversal patterns and managing level-based computations. Developers familiar with BFS level-order traversal usually solve it quickly once they recognize that each tree row corresponds to a BFS level.
Find Largest Value in Each Tree Row Python/Java solution
Python and Java solutions typically implement BFS using a queue or DFS with recursion. Both versions maintain a list that stores the maximum value per level while traversing the tree. Each solution runs in O(n) time and requires O(w) or O(h) space depending on the traversal strategy.
How to solve Find Largest Value in Each Tree Row in O(n)?
Traverse the tree once while maintaining the maximum value for each level. With BFS, process nodes level by level using a queue and track the largest value in each iteration. With DFS, pass the current depth during recursion and update the maximum value stored for that level. Both approaches ensure each node is processed only once.
What is the best approach for Find Largest Value in Each Tree Row?
Breadth-First Search (BFS) using level-order traversal is the most straightforward approach. It processes the tree one level at a time using a queue and computes the maximum value for each row during the traversal. The algorithm runs in O(n) time and uses O(w) space where w is the maximum width of the tree.
Is Find Largest Value in Each Tree Row asked at Google/Amazon/Meta?
Variants of this problem appear in interviews at large tech companies because it tests tree traversal fundamentals. Companies like Amazon, Google, and Meta frequently ask binary tree problems that require BFS level traversal or DFS with depth tracking.
What data structure is used in Find Largest Value in Each Tree Row?
The BFS approach uses a queue to process nodes level by level. The DFS approach relies on recursion (or an explicit stack) along with an array or list that stores the maximum value found for each depth level.
What is the time complexity of Find Largest Value in Each Tree Row?
The optimal time complexity is O(n) because every node in the binary tree is visited exactly once. Both BFS level-order traversal and DFS with depth tracking achieve this complexity while computing the maximum value for each level.