DEV Community

Cover image for Find Largest Value in Each Tree Row
Ashis Chakraborty
Ashis Chakraborty

Posted on

Find Largest Value in Each Tree Row

Leetcode daily challenge: 25 Dec,2024.
Problem link

BFS is perfect when we are dealing specifically with rows/levels of a binary tree. With BFS, we handle one row of the tree at a time.

Here, we need to find the maximum value in each row. We can simply perform a BFS and for each row, keep track of the maximum value we have seen so far.

void bfs( TreeNode* node, vector<int>& result){

        queue<TreeNode *>Q;
        Q.push(node);

        int qSize = Q.size();
        int count =0;

        while(!Q.empty()){
            count = 0;
            priority_queue<int>heap;
            qSize = Q.size();

            while(count<qSize){// for each level/row find max value
                count++;
                TreeNode* temp = Q.front();
                Q.pop();
                heap.push(temp->val);

                if(temp->left != NULL)
                Q.push(temp->left);

                if(temp->right != NULL)
                Q.push(temp->right);

            }//while ends

            if(heap.size())
            result.push_back(heap.top());
        }
    }
    vector<int> largestValues(TreeNode* root) {
        if(root == NULL)
        return {};

        vector<int>result;
        bfs(root, result);///call bfs

        return result;
    }
Enter fullscreen mode Exit fullscreen mode

Video link with detailed explanation will be found here.

Top comments (0)