Problem overview
The function max_sum_bst receives the root of a binary tree, an Option<Box<TreeNode>>, and returns the largest sum of values over all subtrees that are binary search trees (BSTs). In a BST, 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. The empty BST counts, with sum 0, so the answer is never negative. The tree has at most 40,000 nodes and the values are between -40,000 and 40,000.
For [1, 4, 3, 2, 4, 2, 5, null, null, null, null, null, null, 4, 6] the answer is 20: the subtree at 3 (children 2 and 5, with 5's children 4 and 6) is a BST, and 3 + 2 + 5 + 4 + 6 = 20. For [4, 3, null, 1, 2] the answer is 2: the subtree rooted at 3 is not a BST, because its right child 2 is smaller than 3, so the best BST is the single node 2
Approach: each subtree reports four facts
The straightforward solution checks every subtree separately, scanning it again and again. This one visits each node only once, bottom up. A post-order DFS handles the children first, and each call returns four facts about its subtree to the parent:
- whether the subtree is a BST;
- its minimum value;
- its maximum value;
- its sum.
With these four numbers from both children, a node can decide in constant time whether it is the root of a BST. It is, if both children are BSTs, its value is strictly greater than the maximum of its left subtree, and strictly smaller than the minimum of its right subtree. No scan of the subtree is needed, because the minimum and the maximum already summarise it. If the node is a BST root, its subtree sum is a candidate for the answer.
An empty subtree needs values that never break the test. It is a BST with sum 0, and its minimum is the largest possible number, i32::MAX, while its maximum is the smallest, i32::MIN. Then node.val <= left_max is false for an empty left side, and node.val >= right_min is false for an empty right side, so the missing side never blocks the node.
The minimum, maximum and sum are computed for every subtree, even one that is not a BST, because the parent needs them. If a subtree isn't a BST, then none of its ancestors can be either, since an ancestor's subtree contains it. The flag carries that fact upwards.
Step by step
- Keep the best answer in a mutable
result, starting at 0, and pass it down by mutable reference. - Call the helper
Solution::dfs_helper(&root, &mut result), ignore the tuple it returns, and endmax_sum_bstwithresult. - Set up the helper. It takes
root: &Option<Box<TreeNode>>andresult: &mut i32, and returns(bool, i32, i32, i32): is it a BST, minimum, maximum, sum. Its body is amatchonroot. - Empty subtree: the
Nonearm returns(true, i32::MAX, i32::MIN, 0). - Left child: in the
Some(node)arm, call the helper on&node.leftand destructure the result intois_left_bst,left_min,left_maxandleft_sum. - Right child: do the same on
&node.right. Both children are processed before the node, which makes the traversal post-order. - Start the flag:
is_root_bstis alet mutset tois_left_bst && is_right_bst. - Sum:
root_sum = node.val + left_sum + right_sum. It is needed even if this subtree is not a BST. - Minimum and maximum:
root_minisleft_min.min(right_min).min(node.val), androot_maxis the same withmax. - Apply the BST rule: if
node.val <= left_max || node.val >= right_min, setis_root_bsttofalse. The comparisons are strict in the definition, so equal values also break it. - Update the answer: if
is_root_bstis still true, set*resultto the larger of itself androot_sum. - Report upwards: end the arm with the tuple
(is_root_bst, root_min, root_max, root_sum).
The solution in Rust
impl Solution {
fn dfs_helper(root: &Option<Box<TreeNode>>, result: &mut i32) -> (bool, i32, i32, i32) {
match root {
None => (true, i32::MAX, i32::MIN, 0),
Some(node) => {
let (is_left_bst, left_min, left_max, left_sum) =
Solution::dfs_helper(&node.left, result);
let (is_right_bst, right_min, right_max, right_sum) =
Solution::dfs_helper(&node.right, result);
let mut is_root_bst = is_left_bst && is_right_bst;
let root_sum = node.val + left_sum + right_sum;
let root_min = left_min.min(right_min).min(node.val);
let root_max = left_max.max(right_max).max(node.val);
if node.val <= left_max || node.val >= right_min {
is_root_bst = false;
}
if is_root_bst {
*result = (*result).max(root_sum);
}
(is_root_bst, root_min, root_max, root_sum)
}
}
}
fn max_sum_bst(root: Option<Box<TreeNode>>) -> i32 {
let mut result = 0;
Solution::dfs_helper(&root, &mut result);
result
}
}
Rust details that matter here:
- A tuple as a multi-value return.
(bool, i32, i32, i32)returns four values at once, andlet (a, b, c, d) = ...unpacks them into four variables. The call inmax_sum_bstignores the returned tuple, which is allowed: a function call is a valid statement, and the tuple is simply dropped. - Borrowing the tree. The helper takes
&Option<Box<TreeNode>>, and thematchon a reference givesnodeas a reference. The recursion uses&node.leftand&node.right, so nothing is moved or cloned. - Sentinel values.
i32::MAXandi32::MINare associated constants of the integer type. They are the extreme values the type can hold. - Chained
minandmax.left_min.min(right_min).min(node.val)is the smallest of three values, because each call returns ani32that can call the method again. (*result).max(root_sum).resultis a&mut i32, so*resultis the number itself. The parentheses make the dereference happen before the method call.- Passing
resultalong. It is already a mutable reference, so the recursive calls take it as it is. Writing another&mutthere would be a type error. - Value of the match. The tuple at the end of the
Somearm has no semicolon, so it is the value of the arm, and the wholematchis the function's tail expression.
Complexity
Time: O(n). Each node is visited once, and the work per node is a few comparisons and additions, not a scan of its subtree. This is a large improvement over the check-every-subtree approach, whose worst case is cubic: on a chain-shaped tree of 2,000 nodes where every subtree is a BST, the first solution takes about two seconds, while this one takes under a millisecond.
Space: O(h). Only the call stack, as deep as the tree is tall.
Edge cases and common mistakes
- All values negative.
[-4, -2, -5]returns 0.resultstarts at 0, the empty BST. - Equal values.
[2, 2]returns 2. The root equals its left child's maximum, sonode.val <= left_maxholds and the whole tree is not a BST. - A deep value that breaks an ancestor. For
[10, 5, null, null, 15], node 5 with its right child 15 is a BST (sum 20), but at node 10 the left maximum is 15, which is not below 10. The root is not a BST, and the answer is 20. This is why the whole subtree's maximum is needed, not just the child's value. - Empty sides. A node with no left child sees
left_max = i32::MIN, so the first comparison can't fail. If the sentinels were swapped, every leaf would be reported as not a BST. - Checking only the child values. In
[5, 1, 8, null, null, 4], node 8 has the left child 4, which is fine locally. But 4 is in the right subtree of 5 and is smaller than 5, so the tree rooted at 5 is not a BST. Only the right subtree's minimum reveals this. The answer is 12, the subtree rooted at 8. - Overflow. The biggest possible sum is 1,600,000,000, which fits in an
i32.
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.
