Problem overview
The method maxSumBST receives the root of a binary tree and returns the largest sum of the values in any subtree that is a binary search tree (BST). A subtree here is a node together with everything below it. It counts as a BST when the left subtree holds only values strictly smaller than the node, the right subtree holds only values strictly larger, and both of those subtrees are BSTs themselves. An empty tree is allowed as a BST, with sum 0, so the answer is never negative.
Some examples: for the tree with root 2 and children 1 and 3, the whole tree is a BST and the answer is 6. For root 4 with left child 3, whose children are 1 and 2, the answer is 2: the single node 2 is the best BST. For root -4 with children -2 and -5, every value is negative, so the best choice is the empty BST and the answer is 0.
Approach: judge each subtree from what its children report
A direct approach checks every node's subtree with a separate BST test, which repeats a lot of work. A post-order DFS does it in one pass. Post-order means a node is handled after both of its subtrees, so by then everything needed about the children is known.
For each subtree the DFS returns four facts:
- whether the subtree is a BST,
- its minimum value,
- its maximum value,
- the sum of its values.
With these, a node can decide in constant time. It is the root of a BST if both child subtrees are BSTs, its value is strictly greater than the left subtree's maximum, and it is strictly smaller than the right subtree's minimum. Checking the left maximum and the right minimum is enough, because they are the extremes that would break the rule.
Whenever a subtree is a BST, its sum is a candidate for the answer, so the DFS keeps the best one in a field, s.result, while it runs.
An empty subtree needs special numbers. It is a valid BST with sum 0, and it must never cause a parent to fail the check. So it reports the largest possible integer as its minimum and the smallest possible integer as its maximum. Then root.Val <= leftMax and root.Val >= rightMin are false against an empty side, whatever the value is.
The facts of a subtree are reported even when it is not a BST. The minimum, maximum and sum are still correct for it, and the parent needs them. The parent will see the false flag and mark itself as not a BST too.
Step by step
- Add a field to the struct.
result intinsideSolutionholds the best sum found so far, so every method can read and update it. - Reset it in
maxSumBST.s.result = 0. Starting from 0 is what allows the empty BST as the answer, and it also clears the value left by a previous call on the sameSolution. - Run the DFS.
s.dfs(root). Only its effect ons.resultmatters here, so the four returned values are ignored. - Return
s.result. - Declare
dfs. It has the receivers *Solution, takes a*TreeNodeand returns(bool, int, int, int): the flag, the minimum, the maximum and the sum. - Define the sentinels. Two constants,
intMaxandintMin, at the top of the file stand for the largest and smallestint. - Handle the empty subtree. If
root == nil, returntrue, intMax, intMin, 0. - Recurse left. Receive the four results into
isLeftBST,leftMin,leftMaxandleftSum. - Recurse right. The same into
isRightBST,rightMin,rightMaxandrightSum. - Start the flag.
isRootBST := isLeftBST && isRightBST. This is necessary but not sufficient. - Compute the sum.
rootSumisroot.Val + leftSum + rightSum. It is needed even when the subtree is not a BST, because the parent adds it up. - Compute the minimum.
rootMinis the smallest ofleftMin,rightMinandroot.Val, using two nestedmincalls. - Compute the maximum.
rootMaxlikewise withmax. - Check this node's value. If
root.Val <= leftMax || root.Val >= rightMin, setisRootBSTtofalse. The comparisons use<=and>=because equal values also break the rule. - Record a BST. If
isRootBSTis still true, sets.resulttomax(s.result, rootSum). - Return the four facts in the order the parent expects: flag, minimum, maximum, sum.
The solution in Go
const intMax = int(^uint(0) >> 1)
const intMin = -intMax - 1
type Solution struct {
result int
}
func (s *Solution) dfs(root *TreeNode) (bool, int, int, int) {
if root == nil {
return true, intMax, intMin, 0
}
isLeftBST, leftMin, leftMax, leftSum := s.dfs(root.Left)
isRightBST, rightMin, rightMax, rightSum := s.dfs(root.Right)
isRootBST := isLeftBST && isRightBST
rootSum := root.Val + leftSum + rightSum
rootMin := min(min(leftMin, rightMin), root.Val)
rootMax := max(max(leftMax, rightMax), root.Val)
if root.Val <= leftMax || root.Val >= rightMin {
isRootBST = false
}
if isRootBST {
s.result = max(s.result, rootSum)
}
return isRootBST, rootMin, rootMax, rootSum
}
func (s *Solution) maxSumBST(root *TreeNode) int {
s.result = 0
s.dfs(root)
return s.result
}
The Go details worth knowing:
- Methods with a pointer receiver.
func (s *Solution) dfs(...)attaches the function to the type. Because the receiver is a pointer,s.result = ...changes the struct that the caller holds. With a value receiver, each method would work on its own copy and the updates would be lost. Go has no classes: a struct plus methods plays that role. - Multiple return values. The result types are listed in parentheses,
(bool, int, int, int), and a call receives them witha, b, c, d := s.dfs(node). A caller that doesn't need them can ignore them by callings.dfs(root)as a statement, asmaxSumBSTdoes. - The constants.
^uint(0)is an unsigned zero with every bit flipped, which is the largestuint. Shifting it right by one clears the top bit and gives the largestint, and-intMax - 1is the smallest. Themathpackage hasmath.MaxIntandmath.MinIntfor the same purpose, but this program doesn't import it. These are constant expressions, evaluated by the compiler. - Built-in
minandmax. Go 1.21 added them as built-in functions for ordered types, with two or more arguments. The code nests two-argument calls, which reads clearly. - Capitalized
Val. The lesson'sTreeNodehas the exported fieldsVal,LeftandRight.
Complexity
Time: O(n). Each node is visited once, and the work per node is a few comparisons and additions.
Space: O(h). Nothing is stored per node. The only extra memory is the recursion stack, as deep as the tree is tall: O(log n) for a balanced tree and O(n) for a chain. The four values returned by each call live in that stack frame.
Edge cases and common mistakes
- All values negative. The answer is 0, not the largest negative value, because the empty BST is allowed. Starting
s.resultat 0 handles it. For a single node-3, the function returns 0. - Empty tree. A
nilroot returns 0. - Checking only the children's flags. A node whose children are both BSTs can still break the rule through a deeper value. In the tree with root 5 and left child 1, whose right child is 6, the subtree under 1 is a BST, but 6 is larger than 5, so the whole tree is not. The right answer is 7, the sum of the subtree under 1. The min and max facts are what catch this.
- Another deep violation. For root 10 with left child 5, whose right child is 15, and right child 20, the left side is a BST, but 15 is greater than 10. The function returns 20, not the sum of the whole tree.
- Equal values. A node and its child with the same value break the strict rule. A tree with root 5 and left child 5 returns 5, from a single node.
- A larger BST deeper in the tree. The best subtree is not always the biggest one. Updating
s.resultat every node that qualifies is what finds it anywhere. - Forgetting to reset
s.result. If the sameSolutionis used for several trees, the previous answer would leak into the next call. - Wrong sentinels. If an empty subtree returned 0 for both extremes, a leaf with the value -3 would fail
root.Val <= leftMaxagainst its empty left side and be rejected wrongly.
Testing
- Root 2, children 1 and 3, gives 6.
- Root 4, left child 3 with children 1 and 2, gives 2.
- Root -4, children -2 and -5, gives 0.
- Root 5, left 4 (with left child 3), right 8 (with children 6 and 3), gives 7.
- Root 1, left 4 (children 2 and 4), right 3 (left 2, right 5 with children 4 and 6), gives 20.
