Maximum Sum BST

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.

Note : A single leaf node will also act as a BST.

Class TreeNode:
    val (int)
    left (TreeNode)
    right (TreeNode)

Input Format:

First Parameter - root of the tree.

Output Format:

Return the maximum sum of all keys of a binary tree.

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:
    -4 -2 -5
Output:
    0
Explanation:
    All values are negatives. Return an empty BST.

Constraints:

• n = Number of nodes.
• 1 <= n <= 10⁴.
• -4 * 10⁴ <= node.val <= 4 * 10⁴.
• Expected Time Complexity: O(N).
• Expected Space Complexity: O(1).