Last updated on January 12th, 2025 at 03:45 am
Here, we see a Find Largest Value in Each Tree Row LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
String
Companies
Level of Question
Medium
Find Largest Value in Each Tree Row LeetCode Solution
Table of Contents
1. Problem Statement
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]
2. Coding Pattern Used in Solution
The coding pattern used in the provided code is Tree Breadth-First Search (BFS). This pattern involves traversing a tree level by level, processing all nodes at the current level before moving to the next level. The code uses a queue to facilitate this level-order traversal.
3. Code Implementation in Different Languages
3.1 Find Largest Value in Each Tree Row C++
class Solution {
public:
vector<int> largestValues(TreeNode* root) {
if (!root) return {};
vector<int> result;
queue<TreeNode*> queue;
queue.push(root);
while (!queue.empty()) {
int curr_level_size = queue.size();
int max_val = INT_MIN;
for (int i = 0; i < curr_level_size; ++i) {
TreeNode* node = queue.front();
queue.pop();
max_val = std::max(max_val, node->val);
if (node->left) queue.push(node->left);
if (node->right) queue.push(node->right);
}
result.push_back(max_val);
}
return result;
}
};
3.2 Find Largest Value in Each Tree Row Java
class Solution {
public List<Integer> largestValues(TreeNode root) {
if (root == null) return new ArrayList<>();
List<Integer> result = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int curr_level_size = queue.size();
int max_val = Integer.MIN_VALUE;
for (int i = 0; i < curr_level_size; i++) {
TreeNode node = queue.poll();
max_val = Math.max(max_val, node.val);
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
result.add(max_val);
}
return result;
}
}
3.3 Find Largest Value in Each Tree Row JavaScript
var largestValues = function(root) {
if (!root) return [];
const result = [];
const queue = [root];
while (queue.length) {
let curr_level_size = queue.length;
let max_val = Number.MIN_SAFE_INTEGER;
for (let i = 0; i < curr_level_size; i++) {
const node = queue.shift();
max_val = Math.max(max_val, node.val);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
result.push(max_val);
}
return result;
};
3.4 Find Largest Value in Each Tree Row Python
class Solution(object):
def largestValues(self, root):
if not root:
return []
result = []
queue = deque([root])
while queue:
curr_level_size = len(queue)
max_val = float('-inf')
for _ in range(curr_level_size):
node = queue.popleft()
max_val = max(max_val, node.val)
for child in [node.left, node.right]:
if child:
queue.append(child)
result.append(max_val)
return result
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(n) | O(n) |
| Java | O(n) | O(n) |
| JavaScript | O(n) | O(n) |
| Python | O(n) | O(n) |
where, n is the number of nodes in the tree.
- The implementation is identical across all four languages, with minor syntactic differences.
- The BFS pattern ensures that all nodes at a given level are processed before moving to the next level.
- The use of a queue is central to the BFS approach, and the space complexity is dominated by the size of the queue at the widest level of the tree.