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 - 1In #515 Find Largest Value in Each Tree Row, the goal is to determine the maximum value at every depth level of a binary tree. The problem naturally maps to level-wise traversal of the tree.
A common strategy is Breadth-First Search (BFS). Using a queue, traverse the tree level by level. For each level, track the maximum value among all nodes currently in the queue before moving to the next level. This ensures that each row of the tree is processed independently.
Another effective approach is Depth-First Search (DFS). While recursively traversing the tree, keep track of the current depth. If visiting a level for the first time, store the value; otherwise, update the stored value with the maximum of the existing and current node values.
Both methods visit each node exactly once, resulting in efficient traversal with linear time complexity.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Breadth-First Search (Level Order) | O(n) | O(w) where w is the maximum width of the tree |
| Depth-First Search (Recursive) | O(n) | O(h) where h is the height of the tree |
Nick White
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.
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.
1#include <stdio.h>
2#include <stdlib.h>
3#include <limits.h>
4
5// Definition for a binary tree node.
6struct TreeNode {
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.
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.
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.
1#include <vector>
2#include <algorithm>
3#include <climits>
4
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;
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of level-order traversal problems are common in FAANG and other top tech company interviews. This question tests understanding of binary tree traversal, recursion, and level-based processing.
A queue is typically used for the BFS approach to process nodes level by level. For the DFS approach, recursion along with a list or array to store the maximum value at each depth works efficiently.
The optimal approaches are Breadth-First Search (level-order traversal) and Depth-First Search with depth tracking. Both methods visit each node once and keep track of the maximum value at every level of the binary tree.
Yes, DFS works well by tracking the current depth during recursion. You maintain a list where each index represents a level and update the stored value with the maximum encountered at that depth.
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.