Problem overview
The method maxSumBST receives the root of a binary tree, a TreeNode | null, and returns the largest sum of the keys of any subtree that is also a binary search tree (BST). Keys in the left subtree must be strictly smaller than the node's key, keys in the right subtree strictly larger, and both subtrees must be BSTs. An empty BST is allowed, so the answer is never below 0.
In [2,1,3] the whole tree is a BST with sum 6. In [5,4,8,3,null,6,3] the whole tree fails, and so does the subtree at 8, whose left child 6 is fine but whose right child 3 is smaller than 8. The best BST is the subtree at 4, whose sum is 4 + 3 = 7. In [-4,-2,-5] all sums are negative, so the answer is 0.
Approach: ask each subtree for four facts
A simple solution checks every subtree from scratch, scanning its nodes to test the BST rule and to add them up. That re-reads the same nodes for every ancestor and gets slow on large, unbalanced trees.
The faster idea is to read each node once and let the children report what the parent needs. A post-order walk visits the children before the node. If each child returns four facts about its subtree, the node can decide in constant time:
- whether the subtree is a BST;
- its smallest value;
- its largest value;
- its sum.
A node with value v roots a BST exactly when both child subtrees are BSTs, the left subtree's maximum is below v and the right subtree's minimum is above v. The minimum and maximum make the "everything on the left is smaller" test a single comparison instead of a scan.
An empty subtree needs special values so that it never blocks a parent. It is a valid BST with sum 0, its minimum is +Infinity and its maximum is -Infinity. Then any value v is above the empty left side's maximum and below the empty right side's minimum, so the checks pass without special cases. The same values also never win a Math.min or Math.max against a real value.
Whenever a subtree passes, the walk compares its sum with the best so far, which starts at 0 for the empty BST.
Step by step
- Keep the best answer in a field. Declare
resultas anumberand set it to 0 in a constructor. - Call
dfsonce frommaxSumBST, ignore what it returns for the whole tree, and returnthis.result. - Declare
dfsto return a tuple of four values: a boolean, then three numbers (minimum, maximum and sum). - Handle the empty subtree by returning
true, positive infinity, negative infinity and 0. - Get the left report by calling
dfson the left child and destructuring intoisLeftBST,leftMin,leftMaxandleftSum. - Get the right report the same way.
- Start with
isRootBSTastrueonly when both children are BSTs. It is declared withletbecause a later check may turn it off. - Compute the sum of this subtree: the node's value plus both child sums. This is needed even when the subtree is not a BST, because the parent receives it.
- Compute the minimum and maximum of the subtree by nesting two
Math.minor twoMath.maxcalls with the node's own value. - Check the node against its sides: if the value is at most
leftMaxor at leastrightMin, setisRootBSTtofalse. - Update the answer. If the subtree is still a BST, set
resultto the larger of itself and the sum. - Return the four facts in the order the parent expects: flag, minimum, maximum, sum.
The solution in TypeScript
class Solution {
result: number;
constructor() {
this.result = 0;
}
dfs(root: TreeNode | null): [boolean, number, number, number] {
if (root == null) {
return [true, Number.POSITIVE_INFINITY, Number.NEGATIVE_INFINITY, 0];
}
let [isLeftBST, leftMin, leftMax, leftSum] = this.dfs(root.left);
let [isRightBST, rightMin, rightMax, rightSum] = this.dfs(root.right);
let isRootBST = isLeftBST && isRightBST;
let rootSum = root.val + leftSum + rightSum;
let rootMin = Math.min(Math.min(leftMin, rightMin), root.val);
let rootMax = Math.max(Math.max(leftMax, rightMax), root.val);
if (root.val <= leftMax || root.val >= rightMin) {
isRootBST = false;
}
if (isRootBST) {
this.result = Math.max(this.result, rootSum);
}
return [isRootBST, rootMin, rootMax, rootSum];
}
maxSumBST(root: TreeNode | null): number {
this.dfs(root);
return this.result;
}
}
Walk through [2,1,3]. The leaves 1 and 3 each have empty children, so for leaf 1 the checks 1 <= -Infinity and 1 >= Infinity are both false. It is a BST with minimum 1, maximum 1 and sum 1, and the same goes for 3. At the root 2, leftMax is 1 and rightMin is 3, so 2 passes both checks. The sum is 6, and result becomes 6.
The TypeScript details worth a closer look:
- Tuple return type.
[boolean, number, number, number]promises an array of exactly four elements in that order. It is an ordinary array at run time. The destructuring on the receiving side relies on the same order. Number.POSITIVE_INFINITYandNumber.NEGATIVE_INFINITY. They are the same values asInfinityand-Infinity. They work in comparisons: any finite number is less than the first and greater than the second.Math.mintakes several arguments, so the nested calls could also be writtenMath.min(leftMin, rightMin, root.val). The nesting is equivalent.- Return values and fields. The tuple carries facts upward, while
this.resultcollects the best answer found anywhere. The call inmaxSumBSTignores the tuple for the root. - State on the object. The field persists as long as the object does, so reusing one
Solutionobject for a second tree would start from the previous answer.
Complexity
Let n be the number of nodes and h the height.
Time: O(n). Each node is processed once, and the work at a node (a few additions and comparisons) does not depend on the size of its subtrees. This is the improvement over checking each subtree from scratch, which can be cubic on a chain-shaped tree.
Space: O(h). The only extra memory is the recursion, with a four-element array per call. It is O(log n) for a balanced tree and O(n) for a chain.
Edge cases and common mistakes
- All negative values. The answer is 0, because
resultstarts there and the empty BST is allowed. - A non-BST node still reports its sum. The sum is computed before the BST check and returned in all cases. Otherwise the parents above would get wrong totals.
- A non-BST node still reports a real minimum and maximum, but its flag is
false, which stops every ancestor from counting it as part of a BST. - Equal keys. The comparisons use
<=and>=to reject a node, so a duplicate on either side breaks the BST.[2,2]gives 2: each single node is a BST, but together they are not. - Using the direct children only. Comparing the node with its children's values would miss a deeper violation. The subtree's maximum and minimum carry that information up.
- Wrong sentinels. If an empty subtree returned 0 for both bounds, a positive leaf would fail
root.val <= leftMax. The infinities are what make the empty case harmless. - Reordering the tuple. The parent destructures by position. Swapping the minimum and maximum in the return would silently break the checks.
Testing
[2,1,3]gives6.[4,3,null,1,2]gives2.[-4,-2,-5]gives0.[5,4,8,3,null,6,3]gives7.[10,5,15,null,null,6,20]gives41.[1,4,3,2,4,2,5,null,null,null,null,null,null,4,6]gives20.