Problem overview
The method maxSumBST receives the root of a binary tree and returns the largest sum of the keys in any subtree that is also a binary search tree (BST). A subtree is a node together with everything below it. It is a BST when, at every node, all keys in the left subtree are strictly less than the node's key, all keys in the right subtree are strictly greater, and both subtrees are BSTs themselves. Keys can be negative, and the tree has up to 40,000 nodes.
In the tree [2,1,3], the whole tree is a BST, and its sum is 6. In [4,3,null,1,2], node 3 has a right child 2 that is smaller than 3, so the subtree at 3 is not a BST, and neither is the whole tree. The single-node subtrees are, and the best of them is 2. In [-4,-2,-5] every key is negative, and the answer is 0: an empty tree counts as a BST with sum 0. In [5,4,8,3,null,6,3] the node 8 has a right child 3 smaller than itself, so neither it nor the root is a BST. The subtree at node 4, with its child 3, is, and its sum is 7.
Approach: test every subtree, keep the best sum
The idea is the direct one. Visit every node. For each, ask whether the subtree rooted there is a BST, and if so, compute its sum and update the best answer so far. That needs three helpers:
sum(root): the total of a subtree's keys.isBST(root): whether a subtree is a BST.everythingLessandeverythingGreater: whether every key in a subtree is below, or above, a given value.
The last pair matters because checking only a node against its immediate children is not enough. In [5,4,6,null,null,3,7], node 6 has children 3 and 7, which are on the correct sides of 6. But 3 sits in the right subtree of 5 and is smaller than 5, so the whole tree is not a BST. Comparing every key of the left subtree with the node, and every key of the right subtree with the node, catches this. In that example the subtree at 6 is a BST with sum 16, and the answer is 16.
The result field starts at 0, which covers the empty-BST case: negative-only trees return 0 because no BST sum beats it.
This approach is simple but repeats work: each node's check re-walks its subtree. A faster approach does one pass and returns, for every subtree, whether it is a BST together with its smallest key, its largest key and its sum. The lesson keeps the simpler check.
Step by step
- Store the best sum in a struct field.
Solutiongets a fieldresultof typeint. Go gives it the zero value 0, so it needs no initialization. - Write
maxSumBST. It callss.dfs(root)and returnss.result. - Declare
dfswith the same pointer receivers *Solution. A pointer receiver means that updatings.resultchanges the shared struct, not a copy. - Stop on
nil: a barereturnends a method that returns nothing. - Visit the children, left and then right, so every subtree below is examined.
- Test this subtree with
s.isBST(root). - Update the best sum with
s.result = max(s.result, s.sum(root)). - Write
sum. An empty subtree sums to 0; otherwise the sum is the node's value plus the sums of its two subtrees. - Write
isBST. An empty tree is a BST. For a node, combine four checks with&&: the left subtree is a BST, the right subtree is a BST, everything on the left is less than the node's value, and everything on the right is greater. - Write
everythingLess. An empty subtree passes. Otherwise the node's value must be less thanval, and both subtrees must pass with the sameval. - Write
everythingGreaterthe same way with the comparison reversed.
The solution in Go
type Solution struct {
result int
}
func (s *Solution) sum(root *TreeNode) int {
if root == nil {
return 0
}
return root.Val + s.sum(root.Left) + s.sum(root.Right)
}
func (s *Solution) everythingLess(root *TreeNode, val int) bool {
if root == nil {
return true
}
return root.Val < val &&
s.everythingLess(root.Left, val) &&
s.everythingLess(root.Right, val)
}
func (s *Solution) everythingGreater(root *TreeNode, val int) bool {
if root == nil {
return true
}
return root.Val > val &&
s.everythingGreater(root.Left, val) &&
s.everythingGreater(root.Right, val)
}
func (s *Solution) isBST(root *TreeNode) bool {
if root == nil {
return true
}
return s.isBST(root.Left) &&
s.isBST(root.Right) &&
s.everythingLess(root.Left, root.Val) &&
s.everythingGreater(root.Right, root.Val)
}
func (s *Solution) dfs(root *TreeNode) {
if root == nil {
return
}
s.dfs(root.Left)
s.dfs(root.Right)
if s.isBST(root) {
s.result = max(s.result, s.sum(root))
}
}
func (s *Solution) maxSumBST(root *TreeNode) int {
s.dfs(root)
return s.result
}
The Go details worth a closer look:
- Methods and receivers.
func (s *Solution) sum(...)attaches the function to the typeSolution, andsplays the role ofthisorself. Go has no classes; a struct with methods does the job. - Why a pointer receiver. With a value receiver,
swould be a copy, anddfswould update the copy. The pointer receiver lets every method share oneresult. - Zero values. A struct field that is never assigned holds the zero value of its type, 0 for an
int. That is whyresultneeds no constructor. - A
&&chain across lines. Go inserts a semicolon at the end of a line that could end a statement. A line that ends with&&can't, so the expression continues on the next line. A line that began with&&would be an error. - Short-circuit evaluation.
&&stops at the firstfalse, so a failed check skips the more expensive ones after it. - Built-in
max. Since Go 1.21 it needs no import. - Methods in any order.
dfsis written below the helpers it calls, but Go does not require declaration before use at package level.
Complexity
Time. dfs makes one call per node. For each node it runs isBST and sum over that node's subtree. In isBST, every node triggers everythingLess or everythingGreater over a part of its own subtree, so one isBST call on a subtree of m nodes costs up to O(m·h), where h is the subtree's height. On balanced trees, h is about log n, and the total is modest. On a tree that degenerates into a chain, h approaches n, and the total grows much faster, up to about O(n³). A single-pass version that returns minimum, maximum and sum from each subtree runs in O(n).
Space: O(h) for the recursion stack, plus the one integer in the struct.
Edge cases and common mistakes
- All keys negative. The answer is 0, not the largest key. Starting
resultat 0 and updating withmaxgives that for free. - Checking only direct children. The tree
[5,4,6,null,null,3,7]fools a check of immediate children. It must compare each key with the ancestors' bounds, whicheverythingLessandeverythingGreaterdo. - Duplicates. The comparisons are strict, so a repeated key breaks the BST property. A node with a right child of the same key is not a BST.
- A BST inside a non-BST. A bad root doesn't rule out good subtrees. That is why
dfstests every node and does not stop at the first failure. - Reusing one
Solution.resultlives in the struct. CallingmaxSumBSTtwice on the sameSolutionvalue keeps the first call's result, so each tree needs a fresh&Solution{}unless the field is reset. - A bigger sum from a bigger tree is not guaranteed. A larger BST can have a smaller sum than one of its parts when it contains negative keys. The code takes the maximum over all of them.
Testing
[1,4,3,2,4,2,5,null,null,null,null,null,null,4,6]gives20, the subtree at node 3.[4,3,null,1,2]gives2.[-4,-2,-5]gives0.[2,1,3]gives6.[5,4,8,3,null,6,3]gives7.[5,4,6,null,null,3,7]gives16.