Given a binary tree root, return the maximum sum of all keys of any sub-tree which is also a Binary Search Tree (BST).

Assume a BST is defined as follows:


	The left subtree of a node contains only nodes with keys less than the node's key.
	The right subtree of a node contains only nodes with keys greater than the node's key.
	Both the left and right subtrees must also be binary search trees.


&nbsp;
Example 1:



Input: root = [1,4,3,2,4,2,5,null,null,null,null,null,null,4,6]
Output: 20
Explanation: Maximum sum in a valid Binary search tree is obtained in root node with key equal to 3.


Example 2:



Input: root = [4,3,null,1,2]
Output: 2
Explanation: Maximum sum in a valid Binary search tree is obtained in a single root node with key equal to 2.


Example 3:

Input: root = [-4,-2,-5]
Output: 0
Explanation: All values are negatives. Return an empty BST.


&nbsp;
Constraints:


	The number of nodes in the tree is in the range [1, 4 * 104].
	-4 * 104 &lt;= Node.val &lt;= 4 * 104


# 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:
    def maxSumBST(self, root: Optional[TreeNode]) -> int:
        # declaire a variable maxSum to hold the max path sum
        self.maxSum=0
        def getMax(root):
            # return max,min,val - if root is null, valid BST
            if not root : return (float("-inf"),float("inf"),0)
            # traverse left and right part
            leftMax,leftMin,leftMaxSum=getMax(root.left)
            rightMax,rightMin,rightMaxSum=getMax(root.right)
            # if a valid BST
            if root.val>leftMax and root.val<rightMin:
                # update maxSum
                self.maxSum=max(self.maxSum,root.val+leftMaxSum+rightMaxSum)
                # return maximum and minimum node values starting from that node and pathSum
                return max(root.val,rightMax),min(root.val,leftMin),root.val+leftMaxSum+rightMaxSum
            # if not a BST - set an impossible condition such than the root is also returned as non-BST
            return  (float("inf"),float("-inf"),0)
        getMax(root)    
        return self.maxSum
        
            
class Solution {

    int ans = 0;
    public int maxSumBST(TreeNode root) {
        solve(root);
        return ans;
    }
    // int[] = { min, max, sum };
    private int[] solve(TreeNode root) {
        if(root == null)
            return new int[] { Integer.MAX_VALUE, Integer.MIN_VALUE, 0 };

        int[] left = solve(root.left);
        int[] right = solve(root.right);

        if(root.val > left[1] && root.val < right[0]) {
             int sum = left[2] + right[2] + root.val;
             ans = Math.max(ans, sum);
             return new int[] { Math.min(left[0], root.val), Math.max(root.val, right[1]), sum };
        }

        return new int[] { Integer.MIN_VALUE, Integer.MAX_VALUE, 0 };
    }

}
class Solution {
public:
    int ans = 0 ;

    array<int,4> solve(TreeNode * root){
        if(!root) return {1,0,INT_MIN,INT_MAX} ;

        array<int,4> l = solve(root->left) ;
        array<int,4> r = solve(root->right) ;

        if(l[0] and r[0]){
            if(root->val > l[2] and root->val < r[3]){
                ans = max({ans,l[1],r[1]}) ;
                return {1,l[1] + r[1] + root->val,max({root->val,l[2],r[2]}),min({root->val,l[3],r[3]})} ;
            }
        }

        return {0,max(l[1],r[1]),INT_MIN,INT_MAX} ;
    }

    int maxSumBST(TreeNode* root) {
        auto arr = solve(root) ;
        return max(ans,arr[1]) ;
    }
};
var maxSumBST = function(root) {
    let max = 0;
    const dfs = (node) => {
        // NoNode
        if(!node) return [true, 0, Infinity, -Infinity];

        // LeafNode
        if(node && !node.left && !node.right) {
            max = Math.max(max, node.val);
            return [true, node.val, node.val, node.val]
        };

        const [isLeftValid, leftVal, leftMin, leftMax] = dfs(node.left);
        const [isRightValid, rightVal, rightMin, rightMax] = dfs(node.right);

        /**
        * To establish that the current node is also a valid BST, we need to verify the following:
        * 1. Left sub tree is a valid BST
        * 2. Right sub tree is a valid BST
        * 3. The values in the left BST are smaller than current node's value
        * 4. The values in the right BST are greater than current node's value
        **/
        if(isLeftValid && isRightValid && node.val > leftMax && node.val < rightMin) {
            max = Math.max(max, leftVal + rightVal + node.val);
            return [
                true,
                leftVal + rightVal + node.val,
                /**
                * 12
                * / \
                * 8 16
                * \ /
                * 9 15
                * \ /
                * 10 14
                * \ /
                * Infinity -Infinity
                * [Infinity and -Infinity are to depict NoNode cases]
                **/
                Math.min(node.val, leftMin),
                Math.max(node.val, rightMax)
            ];
        }

        return [false, 0, leftMax, rightMin];
    }
    dfs(root);

    return max;
};
Maximum Sum BST in Binary Tree