# Week 4 Session 2 Solutions
## [Max BST Sum](https://leetcode.com/problems/maximum-sum-bst-in-binary-tree)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    """
    post-order traversal
    - if node is a leaf, then pass back its value, minVal, maxVal, isBST
    - if not, then traverse left subtree then right subtree to figure out whether or not
    they are BSTs
    - once you have those values, figure out whether the current node is also a BST by checking
    if isBST is True for both children and all keys of left subtree are < the current node and all keys of right subtree
    are > the current node
    - update maxSumBST if needed whenever you find a BST node
    
    """
    def maxSumBST(self, root: TreeNode) -> int:
        self.maxSum = 0
        self.maxSumBSTHelper(root)
        return self.maxSum
    
    def maxSumBSTHelper(self, node) -> (bool, int, int, int): # (isValidBST, sum, minVal, maxVal)
        if node == None:
            return (True, 0, float('inf'), float('-inf'))
        
        isLeftValidBST, leftSum, leftMinVal, leftMaxVal = self.maxSumBSTHelper(node.left)
        isRightValidBST, rightSum, rightMinVal, rightMaxVal = self.maxSumBSTHelper(node.right)
        
        if leftMaxVal >= node.val or rightMinVal <= node.val or not isLeftValidBST or not isRightValidBST:
            return (False, 0, float('inf'), float('-inf'))
        
        currSum = node.val + leftSum + rightSum
        self.maxSum = max(self.maxSum, currSum)
        return (True, currSum, min(node.val, leftMinVal), max(node.val, rightMaxVal))