Maximum sub-tree sum in a Binary Tree such that the sub-tree is also a BST

'''
We are given a binary tree, and we need to find the maximum sum of any subtree that is also a BST.

For each node, we need to know whether its subtree is a BST, the sum of that subtree, and the minimum and maximum values in that subtree.

A subtree rooted at a node is a BST if its left and right subtrees are BSTs, the maximum value in the left subtree is less than the node’s value, and the minimum value in the right subtree is greater than the node’s value.

By keeping track of the sum of valid BST subtrees while traversing, we can update the global maximum sum whenever we encounter a valid BST.

If a subtree is not a BST, it cannot contribute to the sum of any larger BST, so we mark it invalid and propagate that up.

Using a post-order traversal (DFS), we compute these values for left and right subtrees first, then determine the validity, sum, min, and max for the current node.

This approach allows us to solve the problem in a single pass with O(N) time and O(H) space, where N is the number of nodes and H is the tree height.
'''

from math import inf

# DFS function outside the class
def dfs(node, ans):
    if not node:
        return True, 0, inf, -inf

    l_bst, l_sum, l_min, l_max = dfs(node.left, ans)
    r_bst, r_sum, r_min, r_max = dfs(node.right, ans)

    if l_bst and r_bst and l_max < node.val < r_min:
        cur_sum = l_sum + r_sum + node.val
        ans[0] = max(ans[0], cur_sum)  # update max sum
        return True, cur_sum, min(l_min, node.val), max(r_max, node.val)

    return False, 0, 0, 0

class Solution:
    def maxSumBST(self, root):
        ans = [0]  # use list to pass by reference
        dfs(root, ans)
        return ans[0]