Problem overview
The function maxSumBST receives the root of a binary tree, a TreeNode?, and returns the largest sum of keys over all subtrees that are binary search trees (BSTs). A BST here follows a strict rule at every node: all keys in the left subtree are less than the node's key, all keys in the right subtree are greater, and both subtrees are BSTs themselves. A tree has at most 40,000 nodes, with values between -40,000 and 40,000.
The empty tree counts as a BST with sum 0. That is why the tree [-4, -2, -5] has the answer 0: every non-empty BST in it has a negative sum, and choosing nothing is better.
In the first example, the best subtree is the one rooted at the node 3. Its left child is 2 and its right child is 5, and 5 has children 4 and 6. The keys 2 < 3 < 5 and 4 < 5 < 6 obey the rule, and 4 is also greater than 3, so the sum 3 + 2 + 5 + 4 + 6 = 20 is a valid BST sum. The whole tree is not a BST, because its root 1 has 4 in its left subtree.
Approach: test every node as a possible BST root
Every node is the root of exactly one subtree. So the direct plan has three parts:
- visit every node;
- ask whether the subtree rooted there is a BST;
- if it is, compute its sum and keep the largest sum seen.
The answer starts at 0, which also covers the empty-BST case.
Each part is a small recursive function. sum adds up a subtree. isBST checks the rule. A BST check has to compare a node with everything in each subtree, not only with its direct children. Take the tree [10, 5, 15, null, null, 6, 20]: every node is correctly placed relative to its own children (5 < 10 < 15 and 6 < 15 < 20), yet the whole tree is not a BST, because 6 lies in the right subtree of 10 and is smaller than 10. Only the subtree rooted at 15 is a BST, so the answer is 6 + 15 + 20 = 41. Two helpers, everythingLess and everythingGreater, scan a whole subtree against one bound.
So isBST(root) holds when:
- both child subtrees are BSTs,
- everything in the left subtree is less than
root.value, and - everything in the right subtree is greater than
root.value.
This lesson prefers clarity over speed: it re-scans subtrees at every node. The second lesson on this problem returns the minimum, maximum and sum from a single pass, so nothing is scanned twice.
Step by step
- Keep the best answer in a property. Declare
resultas avarof typeIntin the class, starting at 0. Every function can read and update it. - Write
maxSumBST. Calldfs(root)to visit all subtrees, then returnresult. - Declare
dfswith aTreeNode?parameter and no return value. - Stop at
null. An empty subtree has nothing to check, so a barereturnends the call. - Visit both children with
dfs, so every node below is handled. - Test this node with
isBST(root), which is written later. - Update the best answer to the larger of
resultandsum(root), usingmaxOf. - Write
sumabove it: 0 fornull, otherwise the node's value plus the sums of the two children. - Write
isBST:truefornull, otherwise the four conditions joined with&&, one per line. - Write
everythingLess:truefornull, otherwise the node's value must be below the bound and the same must hold for both children with the same bound. - Write
everythingGreateras its mirror, with the comparison reversed. The bound is namedvaluein both, becausevalis a Kotlin keyword.
The solution in Kotlin
class Solution {
var result: Int = 0
fun sum(root: TreeNode?): Int {
if (root == null) {
return 0
}
return root.value + sum(root.left) + sum(root.right)
}
fun everythingLess(root: TreeNode?, value: Int): Boolean {
if (root == null) {
return true
}
return root.value < value &&
everythingLess(root.left, value) &&
everythingLess(root.right, value)
}
fun everythingGreater(root: TreeNode?, value: Int): Boolean {
if (root == null) {
return true
}
return root.value > value &&
everythingGreater(root.left, value) &&
everythingGreater(root.right, value)
}
fun isBST(root: TreeNode?): Boolean {
if (root == null) {
return true
}
return isBST(root.left) &&
isBST(root.right) &&
everythingLess(root.left, root.value) &&
everythingGreater(root.right, root.value)
}
fun dfs(root: TreeNode?) {
if (root == null) {
return
}
dfs(root.left)
dfs(root.right)
if (isBST(root)) {
result = maxOf(result, sum(root))
}
}
fun maxSumBST(root: TreeNode?): Int {
dfs(root)
return result
}
}
The Kotlin details worth knowing:
- Properties.
var result: Int = 0is a property of the class, with a getter and setter generated for it. Functions in the class use it by name. Because it is state on the object, a second call tomaxSumBSTon the sameSolutionobject starts with the previous call's answer instead of 0. - Line breaks inside
&&chains. Kotlin ends a statement at the end of the line unless the line cannot be complete. A line that ends with&&needs something after it, so the expression continues. Putting the operator at the start of the next line instead would not work, because the previous line would already be a complete statement. - Short-circuiting.
&&stops at the firstfalse, so after one failed check the remaining, possibly costly, scans are skipped. - Smart casts. After the
nullcheck returns, the compiler treatsrootas non-null, soroot.leftandroot.valueneed no?.. Passingroot.left, which may benull, to a parameter of typeTreeNode?is fine. - A function that returns nothing needs no return type. Its type is
Unit, and the barereturnleaves early. - Naming.
valis a keyword, so a parameter can't be called that, andvalueis used instead.valueis also the name of the node's field, so inside these functionsroot.valueis the node's key andvaluealone is the bound.
Complexity
Let n be the number of nodes and h the height of the tree.
Time: it depends on the shape. The scans in everythingLess, everythingGreater and sum each cost the size of the subtree they walk. isBST on a subtree of size s costs up to O(s * h), because every node below does its own scans. dfs runs that for every node. For a balanced tree the total is around O(n log² n). For a chain-shaped tree, where every node has one child, the worst case reaches O(n³). The early exit of && makes many inputs much cheaper than that, but the second lesson's single pass is the one that keeps O(n) in every case.
Space: O(h). Only the recursion uses memory, and it never goes deeper than the height of the tree.
Edge cases and common mistakes
- All values negative.
[-4, -2, -5]returns 0, becauseresultstarts at 0 and no sum beats it. Starting from the first node's sum or a very small number would return a negative value. - Checking only the direct children. The node's children are not enough: every key in the left subtree must be below the node, which is why the helpers scan whole subtrees.
- Equal keys. The rule is strict.
[5, 5]is not a BST, because the left child is not less than the root. The best BST there is the single node on its own, and the result is 5. - A BST inside a bigger non-BST. The tree
[1, 4, 3, 2, 4, 2, 5, null, null, null, null, null, null, 4, 6]is not a BST, but the subtree at 3 is, and the answer is 20. This is why every node is a candidate and not only the root. - A single node. A leaf is a BST by itself. For
[2, 1, 3]the whole tree is a BST and the answer is 6. - Skipping the recursion on children. Without the two
dfscalls, only the root would be checked.
Testing
[1, 4, 3, 2, 4, 2, 5, null, null, null, null, null, null, 4, 6]gives20.[4, 3, null, 1, 2]gives2.[-4, -2, -5]gives0.[2, 1, 3]gives6.[5, 4, 8, 3, null, 6, 3]gives7.