Problem overview
The method maxSumBST receives the root of a binary tree as a TreeNode? and returns the largest sum of values over all subtrees that are binary search trees. In a BST every value in a node's left subtree is smaller than the node, every value in its right subtree is larger, and both subtrees are BSTs. If no BST has a positive sum, the answer is 0, which stands for an empty BST.
For [2, 1, 3] the whole tree is a BST and the answer is 6. For [-4, -2, -5] every sum is negative and the answer is 0. For [5, 4, 8, 3, null, 6, 3] the best BST is node 4 with its child 3, and the answer is 7.
Approach: each subtree reports four facts
The simple approach tests every subtree from scratch by scanning it, which repeats a lot of work. This lesson computes everything in one post-order pass: handle both children first, then the node, and build the node's facts from its children's facts.
Each call returns a tuple for its subtree:
- whether the subtree is a BST;
- its minimum value;
- its maximum value;
- the sum of its values.
With those four numbers, a node doesn't need to rescan its children. It is the root of a BST when both children are BSTs, its value is greater than the left subtree's maximum and smaller than the right subtree's minimum. Comparing with only the maximum on one side and the minimum on the other is enough, because the maximum is the largest value on the left and the minimum is the smallest on the right.
An empty subtree is a BST with sum 0. Its minimum is Int.max and its maximum is Int.min, which looks backwards but is deliberate: any value is less than the "minimum" of an empty right side, and greater than the "maximum" of an empty left side, so an empty side never blocks the node. When the node's own minimum and maximum are computed, these sentinels also never win against a real value.
Whenever a node is the root of a BST, its sum is a candidate for the answer, and the best one is kept in a property named result.
Take [2, 1, 3]. The leaf 1 returns (true, 1, 1, 1), because its empty children leave its minimum and maximum untouched. The leaf 3 returns (true, 3, 3, 3). At the root, 2 is greater than the left maximum 1 and smaller than the right minimum 3, so it is a BST with minimum 1, maximum 3 and sum 6.
Step by step
- Add the property
var resultand set it to 0, abovemaxSumBST. Swift infersInt. - Plan
maxSumBST. Calldfs(root)and ignore the returned tuple with_ =, then returnresult. Only the effect onresultmatters at the top. - Declare
dfswith one unlabeled parameter,_ root: TreeNode?, returning(Bool, Int, Int, Int). - Handle an empty subtree with
guard let node = root else { ... }, returning(true, Int.max, Int.min, 0). After the guard, usenode. - Get the left facts: call
dfs(node.left)and unpack the tuple intoisLeftBST,leftMin,leftMaxandleftSum. - Get the right facts the same way.
- Start with the children's verdict:
var isRootBST = isLeftBST && isRightBST. It is avarbecause the next check may turn it off. - Compute the sum: the node's value plus both child sums. It is needed even when the subtree is not a BST, because the parent uses it.
- Compute the minimum as the smallest of
leftMin,rightMinandnode.val. - Compute the maximum as the largest of
leftMax,rightMaxandnode.val. - Check the node against its sides. If
node.val <= leftMaxornode.val >= rightMin, setisRootBSTtofalse. Both comparisons are strict, so equal values fail. - Update the answer with
max(result, rootSum)ifisRootBSTis stilltrue. - Return the four facts in the same order the parent unpacks them.
The solution in Swift
class Solution {
var result = 0
func dfs(_ root: TreeNode?) -> (Bool, Int, Int, Int) {
guard let node = root else {
return (true, Int.max, Int.min, 0)
}
let (isLeftBST, leftMin, leftMax, leftSum) = dfs(node.left)
let (isRightBST, rightMin, rightMax, rightSum) = dfs(node.right)
var isRootBST = isLeftBST && isRightBST
let rootSum = node.val + leftSum + rightSum
let rootMin = min(min(leftMin, rightMin), node.val)
let rootMax = max(max(leftMax, rightMax), node.val)
if node.val <= leftMax || node.val >= rightMin {
isRootBST = false
}
if isRootBST {
result = max(result, rootSum)
}
return (isRootBST, rootMin, rootMax, rootSum)
}
func maxSumBST(_ root: TreeNode?) -> Int {
_ = dfs(root)
return result
}
}
Swift details worth a closer look:
- Tuples.
(Bool, Int, Int, Int)is a tuple type. A tuple can be returned from a function and unpacked in one statement:let (isLeftBST, leftMin, leftMax, leftSum) = dfs(node.left)declares four constants at once, in order. guard let. Theelsebranch of aguardmust leave the function, here withreturn. Ifroothas a value, the constantnodeis available for the rest of the function, with no!anywhere.Int.maxandInt.min. They are the largest and smallest values of the 64-bitInt. The code never adds to them, so overflow can't happen; only comparisons use them. Arithmetic overflow in Swift crashes the program, which is a reason to keep sentinels out of sums._ = dfs(root). The function result is a tuple that the caller doesn't need. Assigning it to_says that the value is ignored on purpose, and avoids an unused-result warning.- Mutating a property.
resultis changed inside a method of a class, which Swift allows withoutmutating. The value stays on the object between calls, so use a newSolutionfor each tree. minandmaxnesting. The global functions compare two values here, so three values need two calls.
Complexity
Let n be the number of nodes and h the height of the tree.
Time: O(n). Each node is visited once, plus one cheap call per missing child. Each visit does constant work: a few additions and comparisons on values it already received. Nothing rescans a subtree.
Space: O(h). Only the recursion uses memory, as deep as the tree is tall, which is about log n for a balanced tree and n for a chain. Compared with the first lesson, the running time drops from roughly O(n log² n) for a balanced tree, and O(n³) in the worst case, to linear.
Edge cases and common mistakes
- All negative values.
[-4, -2, -5]returns 0:resultstarts at 0 and only a larger sum replaces it. - A non-BST subtree still reports real numbers. Its minimum, maximum and sum are correct even though the flag is
false, which is why they are computed unconditionally. Its ancestors will fail the check anyway because the flag is passed upward. - Equal values.
[2, 2]returns 2: the root fails the strict check against its left child, so only the single-node subtree counts. - Using the wrong side's extreme. The node must be compared with the maximum of the left side and the minimum of the right side. Comparing with the children's values is not enough, because a node deeper in a subtree can violate the rule.
- Swapped sentinels. If an empty subtree returned
Int.minas the minimum andInt.maxas the maximum, a leaf would fail the check against its own empty children. - Tuple order. The caller unpacks by position. Returning the sum before the minimum would silently mix up the values.
- Reusing the object. A second call on the same
Solutioninstance starts with the oldresult.
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.[2, 2]gives2.
