Find Largest Value in Each Row

LeetCode Daily Challenge: 25 Dec, 2024

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

Introduction

In this article, we will discuss a LeetCode daily challenge problem that involves finding the maximum value in each row of a binary tree. We will explore how to solve this problem using Breadth-First Search (BFS) and provide a code example in C++.

Understanding the Problem

The problem statement is to find the maximum value in each row of a binary tree. This can be achieved by performing a BFS traversal of the tree and keeping track of the maximum value seen so far for each row.

Solution

The solution involves using a BFS traversal of the binary tree. We use a queue to store the nodes at each level and a priority queue to keep track of the maximum value seen so far for each level.

Here is the code example in C++:

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) {
            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);

            count++;
        }

        if (heap.size())
            result.push_back(heap.top());
    }
}

vector<int> largestValues(TreeNode* root) {
    if (root == NULL)
        return {};

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

    return result;
}

Explanation

The bfs function takes a TreeNode* node and a vector<int>& result as input. It initializes a queue Q with the given node and a priority queue heap to keep track of the maximum value seen so far for each level.

The function then enters a loop that continues until the queue is empty. In each iteration, it processes the nodes at the current level by popping them from the queue, pushing their values into the priority queue, and pushing their children into the queue.

Once all nodes at the current level have been processed, the function checks if the priority queue is not empty and pushes the maximum value seen so far for that level into the result vector.

Conclusion

In this article, we have discussed a LeetCode daily challenge problem that involves finding the maximum value in each row of a binary tree. We have provided a code example in C++ that uses BFS to solve the problem. The solution involves using a queue to store the nodes at each level and a priority queue to keep track of the maximum value seen so far for each level.

FAQs

Q: What is Breadth-First Search (BFS)?
A: BFS is a traversal algorithm that visits all the nodes at a given level before moving on to the next level.

Q: How does BFS work in this problem?
A: BFS is used to traverse the binary tree level by level, keeping track of the maximum value seen so far for each level.

Q: What is the time complexity of the solution?
A: The time complexity of the solution is O(N), where N is the number of nodes in the binary tree.

Q: What is the space complexity of the solution?
A: The space complexity of the solution is O(N), where N is the number of nodes in the binary tree.