Maximum Sum BST in Binary Tree

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.

For example:

If the root is [1,4,3,2,4,2,5,null,null,null,null,null,null,4,6], the output should be 20 because the maximum sum in a valid Binary search tree is obtained in root node with key equal to 3 (3+2+4+5+6).

If the root is [4,3,null,1,2], the output should be 2 because the maximum sum in a valid Binary search tree is obtained in a single root node with key equal to 2.

If the root is [-4,-2,-5], the output should be 0 because all values are negatives. Return an empty BST.

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: TreeNode) -> int:
        max_sum = 0

        def dfs(node):
            nonlocal max_sum
            if not node:
                return True, float('inf'), float('-inf'), 0

            left_bst, left_min, left_max, left_sum = dfs(node.left)
            right_bst, right_min, right_max, right_sum = dfs(node.right)

            if left_bst and right_bst and left_max < node.val < right_min:
                current_sum = left_sum + right_sum + node.val
                max_sum = max(max_sum, current_sum)
                return True, min(left_min, node.val), max(right_max, node.val), current_sum
            else:
                return False, float('-inf'), float('inf'), 0

        dfs(root)
        return max_sum

Explanation:

The problem requires us to find the maximum sum of keys in any subtree that is also a Binary Search Tree (BST). A BST has the property that all nodes in the left subtree are less than the root, and all nodes in the right subtree are greater than the root.

Algorithm:

1. DFS Traversal: Perform a Depth-First Search (DFS) traversal of the binary tree.
2. BST Validation: For each node, check if the subtree rooted at that node is a BST.
3. Sum Calculation: If the subtree is a BST, calculate the sum of its nodes.
4. Maximum Sum Tracking: Maintain a variable to track the maximum BST sum found so far.

Code Implementation Details:

• The TreeNode class defines the structure of a node in the binary tree.
• The Solution class contains the maxSumBST method, which takes the root of the binary tree as input and returns the maximum BST sum.
• The dfs function recursively traverses the tree and returns a tuple containing:
  • is_bst: A boolean indicating whether the subtree is a BST.
  • min_val: The minimum value in the subtree.
  • max_val: The maximum value in the subtree.
  • subtree_sum: The sum of the nodes in the subtree.
• Base Case: If the node is None (empty), it's a valid BST with a sum of 0, minimum value of infinity, and maximum value of negative infinity.
• Recursive Step: Recursively call dfs on the left and right subtrees.
• BST Condition: Check if the current node can form a BST:
  • Both left and right subtrees must be BSTs (left_bst and right_bst).
  • The maximum value in the left subtree must be less than the current node's value (left_max < node.val).
  • The minimum value in the right subtree must be greater than the current node's value (node.val < right_min).
• If the BST condition is met, calculate the current subtree's sum (current_sum) and update max_sum if needed.
• Return the appropriate tuple based on whether the current subtree is a BST.

Example:

For the input root = [1,4,3,2,4,2,5,null,null,null,null,null,null,4,6], the algorithm identifies the subtree rooted at node 3 as the BST with the maximum sum (3 + 2 + 5 + 4 + 6 = 20).

Big(O) Analysis

• Time Complexity: O(N), where N is the number of nodes in the binary tree. The dfs function visits each node once.
• Space Complexity: O(H), where H is the height of the binary tree. This is due to the recursive call stack of the dfs function. In the worst case (skewed tree), H can be equal to N, resulting in O(N) space complexity. In the average case (balanced tree), H is log(N), resulting in O(log N) space complexity.

Edge Cases:

1. Empty Tree: If the root is None, the function should return 0, as there are no subtrees.
2. All Negative Values: If all nodes have negative values, the maximum BST sum will be 0 (an empty BST).
3. Single Node Tree: A single-node tree is always a BST, so the maximum sum is the value of that node.
4. Duplicate Values: The problem statement doesn't explicitly state that duplicate values are not allowed, but the BST condition (left_max < node.val < right_min) ensures that nodes with duplicate values in subtrees will not be considered part of a valid BST.

These edge cases are correctly handled by the provided solution.