Find Largest Value in Each Tree Row

Leetcode Problem:

• Find Largest Value in Each Tree Row

Summary

• Given the root of a binary tree, return an array of the largest value in each row of the tree (0-indexed).

Approach

• The solution uses a level order traversal (BFS) approach with a depth-first traversal (DFS) to find the largest value in each row
• It uses a queue to store the nodes at each level and a vector to store the largest values.

Complexity

• O(n), where n is the number of nodes in the tree
• Each node is visited once.

Explanation

• The solution starts by initializing a vector to store the largest values and a queue to store the nodes at each level
• It then performs a level order traversal of the tree using a BFS approach
• At each level, it finds the maximum value and stores it in the vector
• The traversal is done using a DFS approach by recursively visiting the left and right children of each node
• The time complexity is O(n) because each node is visited once, and the space complexity is O(n) because the queue stores the nodes at each level.

Solution Code:

/**
 * 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 ans;
    void traversal(TreeNode* root, int depth){
        if(root == nullptr) return;
        if(ans.size() == depth){
            ans.push_back(root->val);
        } else{
            ans[depth] = max(ans[depth], root->val);
        }
        traversal(root->left, depth + 1);
        traversal(root->right, depth + 1);
    }
    vector largestValues(TreeNode* root) {
        traversal(root, 0);
        return ans;
    }
};