algoadvance

Leetcode 515. Find Largest Value in Each Tree Row

Problem Statement

You are given the root of a binary tree. Your task is to find the largest value in each row of the tree and return these values as a list.

Constraints:

Clarifying Questions

  1. Q: Should the result list indicate the level order of the tree rows? A: Yes, the result list should reflect the level order of the tree’s rows.

  2. Q: What should be the result if the tree is empty? A: If the tree is empty, the output should be an empty list.

Strategy

We will perform a level-order traversal (BFS) of the given binary tree, using a queue to process each node in each row. At each level, we will keep track of the maximum value encountered. By the end of processing all nodes at the current level, the maximum value will be recorded. We will continue this until we’ve processed all levels of the tree.

Code

Here’s the implementation in C++:

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

// 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) {
        if (root == nullptr) return {};
        
        vector<int> result;
        queue<TreeNode*> q;
        q.push(root);
        
        while (!q.empty()) {
            int levelSize = q.size();
            int maxVal = INT_MIN;
            
            for (int i = 0; i < levelSize; i++) {
                TreeNode* currentNode = q.front();
                q.pop();
                
                maxVal = max(maxVal, currentNode->val);
                
                if (currentNode->left != nullptr) q.push(currentNode->left);
                if (currentNode->right != nullptr) q.push(currentNode->right);
            }
            
            result.push_back(maxVal);
        }
        
        return result;
    }
};

// Helper function to build a tree from a vector (used for testing)
TreeNode* buildTree(const vector<int>& nodes, int index = 0) {
    if (index >= nodes.size() || nodes[index] == INT_MIN)
        return nullptr;
    
    TreeNode* root = new TreeNode(nodes[index]);
    root->left = buildTree(nodes, 2 * index + 1);
    root->right = buildTree(nodes, 2 * index + 2);
    
    return root;
}

// Test case example
int main() {
    Solution sol;
    vector<int> treeNodes = {1, 3, 2, 5, 3, INT_MIN, 9};
    TreeNode* root = buildTree(treeNodes);
    vector<int> result = sol.largestValues(root);
    
    for (int val : result)
        cout << val << " ";
    
    return 0;
}

Time Complexity

The time complexity of this solution is O(n), where n is the number of nodes in the tree. This is because we visit each node exactly once during the BFS traversal.

The space complexity is also O(n) in the worst case due to the extra space required for the queue, which, in the case of a perfectly balanced tree, can hold approximately n/2 nodes at the deepest level.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI