Given a **binary tree** `root`

, the task is to 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.

**Example 1:**

Input:root = [1,4,3,2,4,2,5,null,null,null,null,null,null,4,6]Output:20Explanation: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:2Explanation: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:0Explanation:All values are negatives. Return an empty BST.

**Example 4:**

Input:root = [2,1,3]Output:6

**Example 5:**

Input:root = [5,4,8,3,null,6,3]Output:7

**Constraints:**

- Each tree has at most
`40000`

nodes.. - Each node's value is between
`[-4 * 10^4 , 4 * 10^4]`

.

The core challenge of this problem is to identify the largest sum of keys in any subtree that is a valid Binary Search Tree (BST). A BST is defined by the property that for any node, all nodes in its left subtree have keys less than the node's key, and all nodes in its right subtree have keys greater than the node's key. This problem is significant in various applications such as database indexing, where BST properties are leveraged for efficient data retrieval.

To solve this problem, we need to traverse the tree and check each subtree to determine if it is a valid BST and calculate its sum. A naive approach would involve checking each subtree individually, which would be highly inefficient. Instead, we can use a post-order traversal to gather information about each subtree and determine if it forms a valid BST.

The naive solution involves checking each node and its subtrees to see if they form a valid BST and then calculating the sum. This approach is not optimal due to its high time complexity.

An optimized solution involves using a post-order traversal to gather information about each subtree. For each node, we can determine if its left and right subtrees are valid BSTs and use this information to check if the current subtree is a valid BST. We can also keep track of the sum of keys in each subtree and update the maximum sum accordingly.

The algorithm involves a post-order traversal of the tree. For each node, we gather information about its left and right subtrees, including whether they are valid BSTs, their sums, and their minimum and maximum values. Using this information, we can determine if the current subtree is a valid BST and calculate its sum.

- Perform a post-order traversal of the tree.
- For each node, gather information about its left and right subtrees.
- Check if the current subtree is a valid BST using the gathered information.
- Calculate the sum of keys in the current subtree if it is a valid BST.
- Update the maximum sum if the current subtree's sum is greater than the previous maximum sum.

```
class Solution {
// Class to store information about each subtree
class SubtreeInfo {
boolean isBST;
int sum;
int min;
int max;
SubtreeInfo(boolean isBST, int sum, int min, int max) {
this.isBST = isBST;
this.sum = sum;
this.min = min;
this.max = max;
}
}
private int maxSum = 0;
public int maxSumBST(TreeNode root) {
postOrderTraversal(root);
return maxSum;
}
private SubtreeInfo postOrderTraversal(TreeNode node) {
if (node == null) {
return new SubtreeInfo(true, 0, Integer.MAX_VALUE, Integer.MIN_VALUE);
}
SubtreeInfo left = postOrderTraversal(node.left);
SubtreeInfo right = postOrderTraversal(node.right);
if (left.isBST && right.isBST && node.val > left.max && node.val < right.min) {
int sum = node.val + left.sum + right.sum;
maxSum = Math.max(maxSum, sum);
return new SubtreeInfo(true, sum, Math.min(node.val, left.min), Math.max(node.val, right.max));
} else {
return new SubtreeInfo(false, 0, 0, 0);
}
}
}
```

The time complexity of the optimized solution is O(n), where n is the number of nodes in the tree. This is because we perform a post-order traversal of the tree, visiting each node exactly once. The space complexity is O(h), where h is the height of the tree, due to the recursion stack.

Potential edge cases include:

- Empty tree: The output should be 0.
- Tree with all negative values: The output should be 0, as no valid BST can have a positive sum.
- Tree with only one node: The output should be the value of that node.

To test the solution comprehensively, we should include a variety of test cases:

- Simple cases with small trees.
- Cases with larger trees to test performance.
- Edge cases such as empty trees and trees with negative values.

When approaching such problems, it is important to:

- Understand the problem requirements and constraints thoroughly.
- Break down the problem into smaller sub-problems.
- Consider different approaches and their trade-offs.
- Practice solving similar problems to improve problem-solving skills.

In this blog post, we discussed the problem of finding the maximum sum of keys in any subtree that is a valid BST. We explored a naive solution and an optimized solution using post-order traversal. We also analyzed the time and space complexity of the solution and discussed potential edge cases and testing strategies. Understanding and solving such problems is crucial for improving problem-solving skills and preparing for technical interviews.

For further reading and practice, consider the following resources: