Find Largest Value in Each Tree Row LeetCode Solution

Difficulty Level Medium
Frequently asked in Amazon Apple Facebook LinkedIn SamsungViews 2803

Problem Statement

Find Largest Value in Each Tree Row LeetCode Solution – Given the root of a binary tree, return an array of the largest value in each row of the tree (0-indexed).

Example

Test Case 1:

Input:

root = [1, 3, 4, 5, 3, null, 9]

Output:

[1, 3, 9]

Find Largest Value in Each Tree Row LeetCode Solution

Explanation

1, 3, and 9 are the largest values in their respective rows.

Approach:

Here we need the maximum value in each row i.e in each level. So basically we can do level order traversal level by level and keep track of the maximum value. So basically we are doing BFS here. We need to traverse the tree in BFS while keeping track of the level and the no. of nodes in a level. If we look at the Queue after each iteration in BFS it always contains the exact amount of elements in a level. so no. of elements in that level is equal to the size of the queue, all we have to do is keep track of the maxValue in that level/iteration.

But we can also do DFS here to solve the problem. DFS traverses in a depth-first manner so while traversing we have to keep track of the level and the maxValue at that level and store it in the respective level index of the array. Here we build the array at every node i.e we have to decide whether we have to update the value in the output array or add a new value to the output array.

Code for Find Largest Value in Each Tree Row

Java Program

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> maxValues = new ArrayList<>();
        if(root == null) return maxValues;
        
        Queue<TreeNode> bfs = new LinkedList<>();
        bfs.offer(root);
        
        while(!bfs.isEmpty()){
            int size = bfs.size();
            int count = 0;
            int max = Integer.MIN_VALUE;
      
      // check all the elements in the current level;
            while(count < size){
                TreeNode curr = bfs.poll();
                
        // get the max value
                max = Math.max(max, curr.val);
                
                if(curr.left != null){
                    bfs.offer(curr.left);
                }
                
                if(curr.right != null){
                    bfs.offer(curr.right);
                }
                
                count++;
            }
            
      // store it in the output.
            maxValues.add(max);
        }
        
        return maxValues;
    }
}

C++ Program

/**
 * Definition for a binary tree node.
 * 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) {}
 * };
 */
class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        vector<int> result;
        if(root == NULL)
            return result;
        queue<TreeNode*> q;
        q.push(root);
        int maxVal = INT_MIN;
        
        while(!q.empty()){
            int len = q.size();
            maxVal = INT_MIN;
            for(int idx = 0; idx < len; idx++){
                TreeNode* front = q.front();
                q.pop();
                if(front->val > maxVal){
                    maxVal = front->val;
                }
                
                if(front->left)
                    q.push(front->left);
                if(front->right)
                    q.push(front->right);
            }
            
            result.push_back(maxVal);
        }
        
        return result;
    }
};

Complexity Analysis for Find Largest Value in Each Tree Row LeetCode Solution

Time Complexity: O(n) — We touch every node once
Space Complexity: O(n) — The last level of a full and complete binary tree can have N/2 nodes. The queue stores every level.

Translate »