Find Largest Value in Each Tree Row

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

Example 1:

Input: root = [1,3,2,5,3,null,9]
Output: [1,3,9]

Constraints:

• The number of nodes in the tree will be in the range [0, 104].
• -231 <= Node.val <= 231 - 1

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

Asked in: Facebook Amazon ,Apple

Leetcode Difficulty: Medium

Code:

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
        
class Solution(object):
    
    def find_largest_in_each_row(self, root, level=0, traversed={}):
        
        if not root: return {}
        
        if level in traversed:
            traversed[level]=max(traversed[level], root.val)
        else:
            traversed[level]=root.val
            
        self.find_largest_in_each_row(root.left, level+1, traversed)
        self.find_largest_in_each_row(root.right, level+1, traversed)
        return traversed
    
    def largestValues(self, root):
        """
        root: TreeNode
        return: List[int]
        """
        traversed={}
        return [v for k,v in self.find_largest_in_each_row(root, 0, traversed).items()]

Thought Process / Explanation:

Since we need to print the largest element at every level, we will have to keep track of the level of each node and some kind of counter to store max per level. The information of level can be added in the recursion call itself..and for the counter, we can have an (int, int) dict to store level and max value found till a point for that level.

Thank You!