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:

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

For example, given the following binary tree:

      1
     / \
    4   3
   / \ / \
  2   4 2   5
         / \
        4   6

The expected output should be 20, as the BST subtree:

    3
   / \
  2   5
     / \
    4   6

sums up to 3 + 2 + 5 + 4 + 6 = 20

Another example:

    4
   / \
  3  null
 / \
1   2

The expected output is 2, because it's the largest BST subtree. Edge cases include negative values, and an empty tree (return 0).

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 traverse(node):
            nonlocal max_sum
            if not node:
                return True, float('inf'), float('-inf'), 0

            left_bst, left_min, left_max, left_sum = traverse(node.left)
            right_bst, right_min, right_max, right_sum = traverse(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

        traverse(root)
        return max_sum

Explanation:

The maxSumBST function calculates the maximum sum of node values in any subtree of a given binary tree that is also a Binary Search Tree (BST).

1. TreeNode Class:

   • Defines the structure of a node in the binary tree.
   • Each node has a value (val), a left child (left), and a right child (right).

2. maxSumBST Function:

   • Initializes max_sum to 0. This variable will store the maximum BST sum found so far.
   • Defines a nested function traverse(node) that recursively explores the tree.
   • Calls the traverse function with the root of the tree.
   • Returns the final max_sum.

3. Traverse Function:

   • This recursive function explores the binary tree in a post-order manner.
   • Base Case: If the current node is None, it means we've reached the end of a branch. In this case, it returns:
     • True: Indicating that an empty tree is a valid BST.
     • float('inf'): Representing positive infinity as the minimum value (so that any node will be smaller).
     • float('-inf'): Representing negative infinity as the maximum value (so that any node will be larger).
     • 0: The sum of an empty tree is 0.
   • Recursive Calls: It recursively calls traverse on the left and right subtrees.
   • BST Check: It checks if the current subtree (rooted at node) is a valid BST. A subtree is a BST if all the following conditions are met:
     • The left subtree is a BST (left_bst is True).
     • The right subtree is a BST (right_bst is True).
     • The maximum value in the left subtree is less than the current node's value (left_max < node.val).
     • The minimum value in the right subtree is greater than the current node's value (node.val < right_min).
   • Update max_sum: If the current subtree is a BST:
     • Calculate the sum of the current subtree (current_sum).
     • Update max_sum with the maximum of the current max_sum and current_sum.
     • Return True, the minimum value in the subtree, the maximum value in the subtree, and the current_sum.
   • Non-BST Case: If the current subtree is not a BST, return False, update min/max to negative/positive infinity (to invalidate parent BST check), and return 0 sum.

Example

Consider the following binary tree:

      1
     / \
    4   3
   / \ / \
  2   4 2   5
         / \
        4   6

The function maxSumBST will return 20. The BST subtree is:

    3
   / \
  2   5
     / \
    4   6

with a sum of 3 + 2 + 5 + 4 + 6 = 20

Time and Space Complexity

• Time Complexity: O(N), where N is the number of nodes in the binary tree. This is because each node is visited once during the traversal.
• Space Complexity: O(H), where H is the height of the binary tree. This is due to the recursive calls of the traverse function. In the worst case (skewed tree), H can be equal to N, resulting in O(N) space complexity. In the best case (balanced tree), H is log(N), resulting in O(log(N)) space complexity.