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!

Symmetric Tree

Problem Statement: Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

Example 1:

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

Constraints:

• The number of nodes in the tree is in the range [1, 1000].
• -100 <= Node.val <= 100

Source: https://leetcode.com/problems/symmetric-tree/

Asked in: Facebook Amazon ,Apple

Leetcode Difficulty: Easy

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 check(self, root1, root2):
        if root1==None and root2==None: return True
        elif root1==None and root2!=None: return False
        elif root1!=None and root2==None: return False
        
        if root1.val==root2.val:
            if self.check(root1.left, root2.right) and self.check(root1.right, root2.left):
                return True
            else:
                return False
        else:
            return False
    
    def isSymmetric(self, root):
        return self.check(root, root)

Thought Process / Explanation:

This problem also follows a typical pattern like other tree problems... we check for the root node and recursively call for left and right parts of the tree. Here, since we spawn two trees,  so the left side of one should be same as the right side of one and vice-versa.

Thank You!

Path Sum

Problem Statement: Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

A leaf is a node with no children.

Example 1:

Input: root = [1,2,3], targetSum = 5
Output: false
Explanation: There two root-to-leaf paths in the tree:
(1 --> 2): The sum is 3.
(1 --> 3): The sum is 4.
There is no root-to-leaf path with sum = 5.

Constraints:

• The number of nodes in the tree is in the range [0, 5000].
• -1000 <= Node.val <= 1000
• -1000 <= targetSum <= 1000

Source: https://leetcode.com/problems/path-sum/

Asked in: Facebook Amazon ,Apple

Leetcode Difficulty: Easy

Code:

    def check(self, root, targetSum, pathSum=0):
        if not root: return
            
        pathSum+=root.val
        
        if pathSum==targetSum and root.left==None and root.right==None: return True
        return self.check(root.left, targetSum, pathSum) or self.check(root.right, targetSum, pathSum)
    
    def haspathsum(self, root, targetSum):
        """
        root: TreeNode
        targetSum: int
        return: bool
        """
        return self.check(root, targetSum)

Thought Process / Explanation:

Keep summing the root values in paths we iterate and compare pathSum with targetSum if the root at that point is a leaf node. Do this for left and right parts of the tree.

Thank You!

Most Frequent Subtree Sum

Problem Statement: Given the root of a binary tree, return the most frequent subtree sum. If there is a tie, return all the values with the highest frequency in any order.

The subtree sum of a node is defined as the sum of all the node values formed by the subtree rooted at that node (including the node itself).

Example 1:

Input: root = [5,2,-3]
Output: [2,-3,4]

Constraints:

• The number of nodes in the tree is in the range [1, 104].
• -105 <= Node.val <= 105

Source: https://leetcode.com/problems/most-frequent-subtree-sum/

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 __init__(self):
        self.subtree_sums = {}
        self.max_freq=-1
        
    def get_max_subtree_sum(self, root):
        if root==None: 
            return 0
        
        leftsum = self.get_max_subtree_sum(root.left)
        rightsum = self.get_max_subtree_sum(root.right)
        currval = root.val
        
        summation = currval + rightsum + leftsum
        self.subtree_sums[summation] = self.subtree_sums.get(summation, 0)+1
        self.max_freq = max(self.max_freq, self.subtree_sums[summation])
        return summation
        
    def findFrequentTreeSum(self, root):
        self.get_max_subtree_sum(root)
        result=[]
        for k,v in self.subtree_sums.items():
            if v==self.max_freq:
                result.append(k)
        return result

Thought Process / Explanation:

We know that sum of the subtree rooted at a certain node is left sum + right sum + curr val. We need to store the sum with it's count and later return only max frequency sum -- for this keeping a dictionary sounds good and also maintaining global max_freq counter for comparison.

Thank You!