Leetcode 515. Find Largest Value in Each Tree Row
Problem Explanation:
Given a binary tree, you are asked to solve for the largest value in each row of the said tree.
Let's walk through an example:
1 2 3Input: 4 5 1 6 / \ 7 3 2 8 / \ \ 9 5 3 9 10 11Output: [1, 3, 9]
This is how it works:
-
The first row only has
1
, so1
is the largest value. -
In the second row, it has values
3
and2
. Among these,3
is the largest. -
In the third row, it has values
5
,3
, and9
. Among these three,9
is the largest.
Hence the output is [1, 3, 9]
.
Approach Explanation:
We will be using Breadth-First Search (BFS) to solve this problem.
We make use of a queue data structure, which helps us in performing the BFS.
We start by adding the root node to the queue. While the queue is not empty, we note down the number of nodes at the current level, sz
, and find the maximum among all these nodes.
We then remove sz
nodes from the front of the queue and add their respective children to the queue. For each of the nodes removed from the queue, we compare it with maxi
, where maxi
is used to store the maximum element in the current level.
Finally, we update maxi
at each step when removing elements from the queue and add it to the ans list which is returned.
Solution
Consider that TreeNode
is a structure/class which has the following three properties:
- val: an integer variable which holds the value of the node.
- left: a pointer to the left child of the node (TreeNode-type).
- right: a pointer to the right child of the node (TreeNode-type).
Python Solution:
1 2Python 3class Solution: 4 def largestValues(self, root): 5 if not root: 6 return [] 7 8 ans = [] 9 q = collections.deque([root]) 10 11 while q: 12 maxi = float('-inf') 13 for _ in range(len(q)): 14 node = q.popleft() 15 maxi = max(maxi, node.val) 16 if node.left: 17 q.append(node.left) 18 if node.right: 19 q.append(node.right) 20 ans.append(maxi) 21 22 return ans
Java Solution:
1 2Java 3public class Solution { 4 public List<Integer> largestValues(TreeNode root) { 5 if (root == null) 6 return new ArrayList<>(); 7 8 List<Integer> ans = new ArrayList<>(); 9 Deque<TreeNode> q = new ArrayDeque<>(); 10 q.offer(root); 11 12 while (!q.isEmpty()) { 13 int size = q.size(); 14 int maxi = Integer.MIN_VALUE; 15 for (int i = 0; i < size; i++) { 16 TreeNode node = q.poll(); 17 maxi = Math.max(maxi, node.val); 18 if (node.left != null) 19 q.offer(node.left); 20 if (node.right != null) 21 q.offer(node.right); 22 } 23 ans.add(maxi); 24 } 25 26 return ans; 27 } 28}
Javascript Solution:
1 2Javascript 3var largestValues = function(root) { 4 if (!root) return []; 5 6 const q = [root]; 7 const ans = []; 8 while (q.length !== 0) { 9 const sz = q.length; 10 let maxi = Number.MIN_SAFE_INTEGER; 11 for (let i = 0; i < sz; i++) { 12 const node = q.shift(); 13 maxi = Math.max(maxi, node.val); 14 if (node.left) q.push(node.left); 15 if (node.right) q.push(node.right); 16 } 17 ans.push(maxi); 18 } 19 return ans; 20};
C++ Solution:
1 2C++ 3class Solution { 4public: 5 vector<int> largestValues(TreeNode* root) { 6 if (root == nullptr) 7 return {}; 8 9 vector<int> ans; 10 queue<TreeNode*> q{{root}}; 11 12 while (!q.empty()) { 13 int maxi = INT_MIN; 14 for (int sz = q.size(); sz > 0; --sz) { 15 TreeNode* node = q.front(); 16 q.pop(); 17 maxi = max(maxi, node->val); 18 if (node->left) 19 q.push(node->left); 20 if (node->right) 21 q.push(node->right); 22 } 23 ans.push_back(maxi); 24 } 25 26 return ans; 27 } 28};
C# Solution:
1
2Csharp
3public class Solution {
4 public IList<int> LargestValues(TreeNode root) {
5 if (root == null)
6 return new List<int>();
7
8 IList<int> ans = new List<int>();
9 Queue<TreeNode> q = new Queue<TreeNode>();
10 q.Enqueue(root);
11
12 while (q.Count > 0) {
13 int sz = q.Count;
14 int maxi = int.MinValue;
15 for (int i = 0; i < sz; i++) {
16 TreeNode node = q.Dequeue();
17 maxi = Math.Max(maxi, node.val);
18 if (node.left != null)
19 q.Enqueue(node.left);
20 if (node.right != null)
21 q.Enqueue(node.right);
22 }
23 ans.Add(maxi);
24 }
25
26 return ans;
27 }
28}
Swift Solution:
1
2Swift
3class Solution {
4 func largestValues(_ root: TreeNode?) -> [Int] {
5 guard let root = root else { return [] }
6 var result = [Int]()
7 var queue = [root]
8 while queue.count > 0 {
9 let size = queue.count
10 var maximum = Int.min
11 for _ in 0 ..< size {
12 let node = queue.removeFirst()
13 maximum = max(maximum, node.val)
14 if let left = node.left {
15 queue.append(left)
16 }
17 if let right = node.right {
18 queue.append(right)
19 }
20 }
21 result.append(maximum)
22 }
23 return result
24 }
25}
Ruby Solution:
1
2Ruby
3def largest_values(root)
4 return [] if root.nil?
5 ans = []
6 queue = [root]
7 while !queue.empty? do
8 max_value = -1.0 / 0
9 size = queue.size
10 size.times do
11 node = queue.shift
12 max_value = [max_value, node.val].max
13 queue << node.left if node.left
14 queue << node.right if node.right
15 end
16 ans << max_value
17 end
18 ans
19end
Kotlin Solution:
1
2kotlin
3fun largestValues(root: TreeNode?): List<Int> {
4 val results = mutableListOf<Int>()
5 if (root != null) {
6 val queue: Queue<TreeNode> = LinkedList()
7 queue.offer(root)
8 while (!queue.isEmpty()) {
9 val size = queue.size
10 var max = Int.MIN_VALUE
11 for (i in 0 until size) {
12 val node = queue.poll()
13 max = Math.max(max, node.`val`)
14 node.left?.let(queue::offer)
15 node.right?.let(queue::offer)
16 }
17 results.add(max)
18 }
19 }
20 return results
21}
Conclusion:
Takeaways from this problem might be to remember the technique of Breadth-First Search (BFS) using a queue and also going level by level and keeping a check of maximum element. Remembering such common patterns can often be useful in solving other similar problems. Total time complexity for above implementations in all the languages is linear in terms of the number of nodes in the tree since we are visiting each node only once, or O(N). The space complexity is also linear since we are using a queue data structure to hold the nodes, or O(N).
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.