Find Largest Value in Each Tree Row

Return the largest element in each row or level of the tree.

Intuition

In these type of problems, we use BFS because it traverses the tree level wise.

At each level, find the maximum element and add it to the result array.

Algorithm

1. If the root is null, return the empty result array.
2. Add root element to the queue.
3. While the queue is not empty, do the following operations

• store the current size of the queue. Because the queue contains the elements of current level
• While iterating through the elements of the current level, track the max value and add left, right nodes to the queue.
• After the iteration, add the max element to the result array

4. return the result array.

Code

class Solution {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null) return res;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty())  {
            int size = queue.size();
            int max = queue.peek().val;
            for(int i = 0; i < size; i++) {
                TreeNode current = queue.remove();
                if(current.val > max) max = current.val;
                if(current.left != null) queue.add(current.left);
                if(current.right != null) queue.add(current.right);
            }
            res.add(max);
        }
        return res;
    }
}

Thanks for reading this article.

Problem : https://leetcode.com/problems/find-largest-value-in-each-tree-row

My profile: https://leetcode.com/patrisrikanth12