Problem overview
The function max_sum_bst receives the root of a binary tree, an Option<Box<TreeNode>>. Some of the tree's subtrees are binary search trees (BSTs), meaning that every value in a node's left subtree is strictly smaller than the node's value, every value in its right subtree is strictly larger, and both subtrees are BSTs themselves. The function returns the largest sum of values over any subtree that is a BST. The tree has at most 40,000 nodes, with values from -40,000 to 40,000.
In the tree [1, 4, 3, 2, 4, 2, 5, null, null, null, null, null, null, 4, 6] the whole tree is not a BST, because 4 is on the left of 1. The subtree rooted at 3 has the left child 2 and the right child 5, whose children are 4 and 6. It is a BST with the sum 3 + 2 + 5 + 4 + 6 = 20, and that is the best one. For [-4, -2, -5] every value is negative, so the best choice is the empty BST with sum 0.
Approach: test each subtree on its own
The statement defines the answer over any subtree, so the plain solution looks at every node, treats it as the root of a subtree and asks two questions:
- Is this subtree a BST?
- If so, what is its sum?
The best sum seen is kept in a running result. It starts at 0, which stands for the empty BST and wins when every candidate is negative.
Testing whether a subtree is a BST follows the definition directly. A node is the root of a BST when both child subtrees are BSTs, everything in its left subtree is less than the node's value, and everything in its right subtree is greater. The checks "everything is less than" and "everything is greater than" are two small recursive helpers. Note that comparing a node only with its direct children is not enough. In the tree with root 10, left child 5 and a right child 15 under the 5, node 5 is fine on its own, but 15 is on the left side of 10 and breaks the rule for the whole tree. The helpers scan the entire subtree for exactly this reason.
This approach is easy to get right, but it repeats work: is_bst and sum are recomputed from scratch for every node. The lesson has a second solution that avoids that by having each subtree report its facts to its parent in one pass.
Step by step
- Keep the best answer in
result, declared withlet mut result = 0insidemax_sum_bst.Solutionhas no fields to hold it, sodfswill receive it by mutable reference. - Call
dfsasSelf::dfs(&root, &mut result), then returnresult. The tree is read-only, so it is borrowed with&. - Declare
dfswith the parametersroot: &Option<Box<TreeNode>>andresult: &mut i32. It returns nothing. - Handle only real nodes with
if let Some(node) = root. - Visit both children first: call
Self::dfson&node.leftand&node.rightwithresult, so every subtree below is examined. - Test the current subtree: if
Self::is_bst(root)is true, updateresultwith the larger of its value andSelf::sum(root), written as*result = (*result).max(Self::sum(root)). - Write
sum. Amatchonroot:Nonegives 0, andSome(node)givesnode.valplus the sums of the two children. - Write
everything_lesswith the parametersrootandval: i32. An empty subtree is fine (true). A node passes whennode.val < valand both child subtrees pass with the sameval. - Write
everything_greateras the mirror image withnode.val > val. - Write
is_bst. 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 thannode.val, and everything on the right is greater.
The solution in Rust
impl Solution {
fn sum(root: &Option<Box<TreeNode>>) -> i32 {
match root {
None => 0,
Some(node) => node.val + Self::sum(&node.left) + Self::sum(&node.right),
}
}
fn everything_less(root: &Option<Box<TreeNode>>, val: i32) -> bool {
match root {
None => true,
Some(node) => {
node.val < val
&& Self::everything_less(&node.left, val)
&& Self::everything_less(&node.right, val)
}
}
}
fn everything_greater(root: &Option<Box<TreeNode>>, val: i32) -> bool {
match root {
None => true,
Some(node) => {
node.val > val
&& Self::everything_greater(&node.left, val)
&& Self::everything_greater(&node.right, val)
}
}
}
fn is_bst(root: &Option<Box<TreeNode>>) -> bool {
match root {
None => true,
Some(node) => {
Self::is_bst(&node.left)
&& Self::is_bst(&node.right)
&& Self::everything_less(&node.left, node.val)
&& Self::everything_greater(&node.right, node.val)
}
}
}
fn dfs(root: &Option<Box<TreeNode>>, result: &mut i32) {
if let Some(node) = root {
Self::dfs(&node.left, result);
Self::dfs(&node.right, result);
if Self::is_bst(root) {
*result = (*result).max(Self::sum(root));
}
}
}
fn max_sum_bst(root: Option<Box<TreeNode>>) -> i32 {
let mut result = 0;
Self::dfs(&root, &mut result);
result
}
}
Rust details that matter here:
- Borrowed trees. Every helper takes
&Option<Box<TreeNode>>. Inmatch rootandif let Some(node) = root, matching a reference givesnodeas a reference, so nothing is moved out of the tree and the same subtree can be examined again and again. The recursive calls use&node.leftand&node.right. (*result).max(...).resultis a&mut i32, so the number is read and written through*result. The parentheses are needed because a method call binds tighter than the*:*result.max(...)would callmaxonresultitself and then apply*to the outcome.- Passing
resulton. Insidedfsit is already a mutable reference, so the recursive calls pass it as it is, and it is usable again after each call. - Final expressions and
&&. The bodies of the match arms have no semicolons, so their values are the values of the functions.&&stops at the firstfalse, which skips the remaining scans.
Complexity
Time: balanced trees are fast, but the worst case is O(n³). For one subtree of size s, sum costs O(s). is_bst calls everything_less and everything_greater at every node of the subtree, and each scans a part of it, so one is_bst call costs the sum of all subtree sizes inside, which is O(s · h) for height h. dfs runs is_bst once for every node. For a tree shaped like a chain in which each value is larger than the one above it, every subtree is a BST, so nothing is cut short. Timing that case with 500, 1,000 and 2,000 nodes shows the work growing by about eight times each time the size doubles. For a balanced tree the cost is far lower, because h is small.
Space: O(h). Nothing is stored except the call stack, whose depth is the height of the tree, which is up to n for a chain.
The second solution for this problem brings the time down to O(n).
Edge cases and common mistakes
- All values negative.
[-4, -2, -5]returns 0. The initialresult = 0is the empty BST. Starting from the first node's value would give a negative answer. - Checking only the direct children. The tree
[10, 5, null, null, 15]has root 10 with a left child 5 whose right child is 15. Comparing each node with its immediate children accepts it, which would give the sum 30. The correct answer is 20, the subtree rooted at 5 (5 + 15), because 15 is on the left side of 10 and is not less than it. - Equal values.
[2, 2]returns 2. The rule is strict, so a node and its left child with the same value is not a BST, and the best BST is a single node. - Single node. A leaf is always a BST. A tree with one node 7 gives 7.
- Forgetting to examine inner subtrees. If only the root is tested, the answer for the first example would be 0 instead of 20. The recursion on the children is what examines every subtree.
- Overflow. The biggest possible sum is 40,000 × 40,000 = 1,600,000,000, which still fits in an
i32. The lessons build with optimizations, where an overflow would wrap silently.
Testing
[1, 4, 3, 2, 4, 2, 5, null, null, null, null, null, null, 4, 6]gives 20.[4, 3, null, 1, 2]gives 2.[-4, -2, -5]gives 0.[2, 1, 3]gives 6.[5, 4, 8, 3, null, 6, 3]gives 7.[10, 5, null, null, 15]gives 20.
