Minimum Subtree – Python 3 (Week 14 – 13)

"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""

class Solution:
    """
    @param root: the root of binary tree
    @return: the root of the minimum subtree
    """
    def findSubtree(self, root):
        # write your code here
        mini, subtree, sum = self.helper(root)
        return subtree

    def helper(self, root):
        
        if root is None:
            return sys.maxsize, None, 0
        
        left_mini, left_subtree, left_sum = self.helper(root.left)
        right_mini, right_subtree, right_sum = self.helper(root.right)
        
        sum = left_sum + right_sum + root.val
        
            
        if left_mini == min(left_mini, right_mini, sum):
            return left_mini, left_subtree, sum
        if right_mini == min(left_mini, right_mini, sum):
            return right_mini, right_subtree, sum
        
        return sum, root, sum