Problem overview
The method MaxSumBST receives the root of a binary tree and returns the largest sum of keys over all subtrees that are binary search trees. A BST requires every key in the left subtree to be strictly smaller than the node's key, every key in the right subtree to be strictly greater, and both subtrees to be BSTs. If every key is negative, the answer is 0, for the empty BST.
For [1, 4, 3, 2, 4, 2, 5, null, null, null, null, null, null, 4, 6] the best subtree is the one rooted at 3. Its left child is 2, its right child is 5, and 5 has children 4 and 6. That is a BST with sum 3 + 2 + 5 + 4 + 6 = 20. The root 1 has a left child 4, which is bigger than 1, so the whole tree is not a BST.
Approach: each subtree reports four facts
The other lesson on this problem tests every subtree from scratch, walking it again for the BST check and again for the sum. In the worst case that costs O(n²). This lesson visits each node once, after its children. That is post-order, and it works because a parent can decide using only a few facts about its children, so nothing has to be walked again.
For each subtree, Dfs returns four numbers:
- whether the subtree is a BST;
- its minimum key;
- its maximum key;
- the sum of its keys.
With these, a node is the root of a BST exactly when both child subtrees are BSTs, root.val is greater than the left maximum, and root.val is smaller than the right minimum. Each condition is one comparison. The sum of a node's subtree is its key plus the two child sums, and the minimum and maximum are updated from the children in constant time.
An empty subtree needs values that never get in the way. It is a valid BST, with sum 0, and its minimum is int.MaxValue and its maximum is int.MinValue. A real parent key is always less than the "minimum" of an empty right side and greater than the "maximum" of an empty left side, so the comparisons pass without special cases.
Step by step
- Keep the best sum in a field,
int result, with the initializer= 0. The field initializer runs when the object is created, so no constructor is needed. - Run the search and return the field.
MaxSumBSTcallsDfs(root), ignores the array it returns, and returnsresult. - Declare
Dfsto take aTreeNodeand return anint[]of four entries: the BST flag, the minimum, the maximum and the sum. Anintarray can't hold abool, so the flag is stored as 1 or 0. - Empty subtree. Return
{1, int.MaxValue, int.MinValue, 0}. - Left report. Call
Dfs(root.left)and unpack it intoisLeftBST(the flag compared with 1),leftMin,leftMaxandleftSum. - Right report. Do the same for the right child.
- Start with the children's verdict.
isRootBSTis true only if bothisLeftBSTandisRightBSTare. - Sum.
rootSumisroot.val + leftSum + rightSum. It's needed even when the subtree is not a BST, because the parent receives it. - Minimum.
rootMinis the smallest ofleftMin,rightMinandroot.val, using two nestedMath.Mincalls. - Maximum.
rootMaxis built the same way withMath.Max. - Check the node's own key. If
root.val <= leftMaxorroot.val >= rightMin, setisRootBSTto false. The comparisons are strict, so equal keys also break the rule. - Update the answer. If
isRootBSTis still true, setresultto the larger ofresultandrootSum. - Return the four facts in the order flag, minimum, maximum, sum. The ternary operator
isRootBST ? 1 : 0converts the flag.
The solution in C#
class Solution {
int result = 0;
public int[] Dfs(TreeNode root) {
if (root == null) {
return new int[]{1, int.MaxValue, int.MinValue, 0};
}
int[] leftSubtree = Dfs(root.left);
bool isLeftBST = leftSubtree[0] == 1;
int leftMin = leftSubtree[1];
int leftMax = leftSubtree[2];
int leftSum = leftSubtree[3];
int[] rightSubtree = Dfs(root.right);
bool isRightBST = rightSubtree[0] == 1;
int rightMin = rightSubtree[1];
int rightMax = rightSubtree[2];
int rightSum = rightSubtree[3];
bool isRootBST = isLeftBST && isRightBST;
int rootSum = root.val + leftSum + rightSum;
int rootMin = Math.Min(Math.Min(leftMin, rightMin), root.val);
int rootMax = Math.Max(Math.Max(leftMax, rightMax), root.val);
if (root.val <= leftMax || root.val >= rightMin) {
isRootBST = false;
}
if (isRootBST) {
result = Math.Max(result, rootSum);
}
return new int[]{isRootBST ? 1 : 0, rootMin, rootMax, rootSum};
}
public int MaxSumBST(TreeNode root) {
Dfs(root);
return result;
}
};
C# details:
- Field initializer.
int result = 0;sets the starting value as part of the declaration. Because 0 is also the default for anintfield, the initializer states the intent rather than changing anything. - Array literal.
new int[]{1, int.MaxValue, int.MinValue, 0}creates and fills an array in one expression. The caller reads it by position, so the order has to be the same on both sides. - Bool to int and back. C# has no implicit conversion between
boolandint.leftSubtree[0] == 1produces abool, andisRootBST ? 1 : 0produces anint. A tuple such as(bool, int, int, int)would avoid this, but the lesson uses arrays. - Sentinels.
int.MaxValueandint.MinValueare the largest and smallestintvalues. They are only compared, never added, so they can't overflow. Sums are added, but they only combine real keys: at most 40,000 keys with magnitude up to 40,000 gives at most 1.6 billion, within theintrange of about 2.1 billion. - The search ignores the returned array at the top level. Calling a method and discarding its result is legal in C#, and the useful effect is the update of
result.
Complexity
Time: O(n). Each node is visited once, and the work per node is a constant number of comparisons and one small array allocation.
Space: O(h) for the recursion, where h is the height of the tree, up to n for a chain. The arrays of finished calls are discarded.
Edge cases and common mistakes
- All keys negative. The field starts at 0, so the answer is 0, the empty BST.
[-4, -2, -5]gives 0. - Leaves. A leaf has two empty children. Their sentinels pass both comparisons, so every leaf is a BST with its own key as the sum.
- Non-BST nodes still report values. Their minimum, maximum and sum are computed in any case. Only the flag is false, so ancestors fail the BST test but still know the correct sums.
- Using
<instead of<=in the check. That would accept a node equal to its left maximum or right minimum. The problem needs strict ordering. - Comparing with the direct children only. Using
root.left.valwould miss a large key deeper in the left subtree. Passing the minimum and maximum up avoids this. - Counting a non-BST sum. Updating
resultbefore the BST test is finished would accept subtrees that are not BSTs. The update comes after the key check.
Testing
[2, 1, 3]gives 6.[4, 3, null, 1, 2]gives 2.[-4, -2, -5]gives 0.[5, 4, 8, 3, null, 6, 3]gives 7.[1, 4, 3, 2, 4, 2, 5, null, null, null, null, null, null, 4, 6]gives 20.