Code Implementation

# 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: TreeNode) -> int:
        self.max_sum = 0
        
        def postorder(node):
            if not node:
                # is_bst, min, max, sum
                return (True, float('inf'), float('-inf'), 0)
            l_bst, l_min, l_max, l_sum = postorder(node.left)
            r_bst, r_min, r_max, r_sum = postorder(node.right)
            if l_bst and r_bst and l_max < node.val < r_min:
                total = l_sum + r_sum + node.val
                self.max_sum = max(self.max_sum, total)
                return (True, min(l_min, node.val), max(r_max, node.val), total)
            else:
                return (False, 0, 0, 0)
        
        postorder(root)
        return self.max_sum
      

// Definition for a binary tree node.
// struct TreeNode {
//     int val;
//     TreeNode *left;
//     TreeNode *right;
//     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
// };
class Solution {
public:
    int maxSum = 0;
    // returns {isBST, min, max, sum}
    vector<int> postorder(TreeNode* node) {
        if (!node) return {1, INT_MAX, INT_MIN, 0};
        auto l = postorder(node->left);
        auto r = postorder(node->right);
        if (l[0] && r[0] && l[2] < node->val && node->val < r[1]) {
            int sum = l[3] + r[3] + node->val;
            maxSum = max(maxSum, sum);
            return {1, min(l[1], node->val), max(r[2], node->val), sum};
        }
        return {0, 0, 0, 0};
    }
    int maxSumBST(TreeNode* root) {
        postorder(root);
        return maxSum;
    }
};
      

// Definition for a binary tree node.
// public class TreeNode {
//     int val;
//     TreeNode left;
//     TreeNode right;
//     TreeNode(int x) { val = x; }
// }
class Solution {
    private int maxSum = 0;
    // returns int[]{isBST, min, max, sum}
    private int[] postorder(TreeNode node) {
        if (node == null) return new int[]{1, Integer.MAX_VALUE, Integer.MIN_VALUE, 0};
        int[] l = postorder(node.left);
        int[] r = postorder(node.right);
        if (l[0] == 1 && r[0] == 1 && l[2] < node.val && node.val < r[1]) {
            int sum = l[3] + r[3] + node.val;
            maxSum = Math.max(maxSum, sum);
            return new int[]{1, Math.min(l[1], node.val), Math.max(r[2], node.val), sum};
        }
        return new int[]{0, 0, 0, 0};
    }
    public int maxSumBST(TreeNode root) {
        postorder(root);
        return maxSum;
    }
}
      

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
var maxSumBST = function(root) {
    let maxSum = 0;
    // returns [isBST, min, max, sum]
    function postorder(node) {
        if (!node) return [true, Infinity, -Infinity, 0];
        let [lBST, lMin, lMax, lSum] = postorder(node.left);
        let [rBST, rMin, rMax, rSum] = postorder(node.right);
        if (lBST && rBST && lMax < node.val && node.val < rMin) {
            let total = lSum + rSum + node.val;
            maxSum = Math.max(maxSum, total);
            return [true, Math.min(lMin, node.val), Math.max(rMax, node.val), total];
        }
        return [false, 0, 0, 0];
    }
    postorder(root);
    return maxSum;
};
      

Problem Description

Given the root of a binary tree, your task is to find the maximum sum of all keys in any subtree which is also a Binary Search Tree (BST). A subtree of a node is considered a BST if:

• Each node's left subtree contains only nodes with keys less than the node's key.
• Each node's right subtree contains only nodes with keys greater than the node's key.
• Both left and right subtrees must also be BSTs.

• Each node's value may be negative or positive.
• We must consider every possible subtree, not just the entire tree or root-based subtrees.

Thought Process

To solve this problem, we need to consider every possible subtree in the binary tree and check if it's a valid BST. If it is, we compute the sum of its nodes and keep track of the maximum found.
The brute-force approach would be to check every node as a root, validate if its subtree is a BST (which itself can be O(n)), and then sum its values. But this would be very inefficient, especially for large trees.
Instead, we can use a more efficient approach by processing the tree in a bottom-up manner (post-order traversal). For each node, we can gather information from its left and right subtrees about:

• Whether the subtree is a BST
• The minimum and maximum values in the subtree
• The sum of all values in the subtree

Solution Approach

The optimized solution uses a post-order traversal (left-right-root) to process each node only once, collecting all the necessary information from its children before processing the parent. Here’s how it works step-by-step:

1. Define the Information to Track:
   • Is the subtree a BST?
   • The minimum value in the subtree (to validate BST property for parent)
   • The maximum value in the subtree (to validate BST property for parent)
   • The sum of all node values in the subtree
2. Base Case:
   For a null node, consider it a valid BST with sum 0, min as +infinity, and max as -infinity. This helps with leaf node handling.
3. Recursive Step:
   For each node, recursively get the above information from the left and right subtrees.
   • If both left and right subtrees are BSTs, and the current node’s value is greater than the max in the left and less than the min in the right, then the current subtree is a BST.
   • Calculate the sum for this subtree. Update the global max sum if this subtree's sum is larger.
   • If not a BST, return a flag indicating so, and dummy values for min, max, and sum (since this subtree can't be part of any BST).
4. Return the Result:
   After traversing the entire tree, the maximum sum found is the answer.

Example Walkthrough

Sample Input:
Consider the following binary tree:

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

• Start at the leaves. Each leaf (2, 4, 4, 6) is a BST of itself with sum equal to its value.
• Move up to node 5: its left (4) and right (6) are BSTs, and 4 < 5 < 6, so subtree rooted at 5 is a BST with sum 4+6+5=15.
• Node 3: left is null, right subtree (5) is BST with min=4, so 3 < 4 (true), but 5's min is 4, so 3 < 4, so subtree rooted at 3 is a BST with sum 3+15=18.
• Node 4 (left child of 1): left=2, right=4. 2 < 4 < 4 is false (since 4 is not less than 4), so not a BST.
• Node 1: left subtree is not BST, so cannot be BST.
• The maximum sum among all BST subtrees is 20 (from the subtree rooted at 3: nodes 3, 5, 4, 6).

Time and Space Complexity

Brute-force Approach:
For each node, check if its subtree is a BST and sum its values. For each node, this takes O(n) time, leading to O(n^2) total time for n nodes.
Optimized Approach (Post-order Traversal):

• Time Complexity: O(n), since each node is visited exactly once and all operations per node are constant time.
• Space Complexity: O(h), where h is the height of the tree (due to recursion stack). In the worst case (skewed tree), h = n; in a balanced tree, h = log n.

Summary

This problem is elegantly solved by using a post-order traversal to gather and propagate BST properties up the tree. By checking BST validity and computing subtree sums as we return from recursion, we efficiently determine the maximum sum of any BST subtree. The key insight is to collect all necessary information from children before processing the parent, enabling an O(n) solution that is both clean and intuitive.