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:
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: root = [-4,-2,-5] Output: 0 Explanation: 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:
40000 nodes..[-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.
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:
To test the solution comprehensively, we should include a variety of test cases:
When approaching such problems, it is important to:
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: