Problem overview
The method maxSumBST receives the root of a binary tree as a TreeNode?. Some of its subtrees (a node together with everything below it) are binary search trees: 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 themselves. The method returns the largest sum of values over all subtrees that are BSTs. If every such sum would be negative, the answer is 0, which stands for an empty BST.
For [2, 1, 3] the whole tree is a BST and the sum is 6. For [-4, -2, -5] the tree is not a BST, and its single-node subtrees have negative sums, so the answer is 0. For [4, 3, null, 1, 2] the root 4 has the left child 3, whose children are 1 and 2. Node 3 is not a BST root because its right child, 2, is smaller than 3, and so node 4 fails too. The single nodes 1 and 2 are BSTs, and the larger sum is 2.
Approach: test each subtree on its own
The plan has three small pieces and one loop that combines them:
sum(root)adds up all values of a subtree.everythingLess(root, val)andeverythingGreater(root, val)check that every value in a subtree is below, or above, a bound.isBST(root)uses them: a tree is a BST when both child subtrees are BSTs, everything on the left is below the node and everything on the right is above it.dfs(root)visits every node and, whenever the subtree rooted there is a BST, updates the best sum seen so far.
The best sum is kept in a property, result, of the Solution class so that every method can reach it. It starts at 0. That start value gives the empty-BST answer for free, because a larger sum replaces it only when it is positive.
Checking against the immediate children's values isn't enough. In a BST, every value in the left subtree must be smaller than the root, not just the left child. This is why everythingLess and everythingGreater walk whole subtrees.
The price is speed. The method re-examines the same nodes many times: every node asks its whole subtree, and every ancestor asks again. It is clear and correct, and the second lesson on this problem removes the repetition.
Step by step
- Add the property
var result: Int = 0abovemaxSumBST. - Plan
maxSumBST. Calldfs(root), then returnresult. The helper returns nothing and leaves the answer inresult. - Declare
dfswith one unlabeled parameter,_ root: TreeNode?, and no return value. - Base case: if
rootisnil, return. - Visit the children first with
dfs(root!.left)anddfs(root!.right), so every smaller subtree is checked. - Test this subtree with
isBST(root), which is written later. - Update the answer inside that
if:result = max(result, sum(root)). - Write
sum. Its base case returns 0 fornil. Otherwise it returns the node's value plus the sums of both children. - Write
isBST. An empty tree is a BST, sonilreturnstrue. - Combine four checks with
&&: the left child is a BST, the right child is a BST, everything on the left is less than the node's value, and everything on the right is greater. - Write
everythingLess(root, val).nilreturnstrue. Otherwise the node's value must be belowval, and the same must hold for both children with the sameval. - Write
everythingGreater(root, val). It mirrors the previous one with the comparison reversed.
The solution in Swift
class Solution {
var result: Int = 0
func sum(_ root: TreeNode?) -> Int {
if root == nil {
return 0
}
return root!.val + sum(root!.left) + sum(root!.right)
}
func everythingLess(_ root: TreeNode?, _ val: Int) -> Bool {
if root == nil {
return true
}
return root!.val < val &&
everythingLess(root!.left, val) &&
everythingLess(root!.right, val)
}
func everythingGreater(_ root: TreeNode?, _ val: Int) -> Bool {
if root == nil {
return true
}
return root!.val > val &&
everythingGreater(root!.left, val) &&
everythingGreater(root!.right, val)
}
func isBST(_ root: TreeNode?) -> Bool {
if root == nil {
return true
}
return isBST(root!.left) &&
isBST(root!.right) &&
everythingLess(root!.left, root!.val) &&
everythingGreater(root!.right, root!.val)
}
func dfs(_ root: TreeNode?) {
if root == nil {
return
}
dfs(root!.left)
dfs(root!.right)
if isBST(root) {
result = max(result, sum(root))
}
}
func maxSumBST(_ root: TreeNode?) -> Int {
dfs(root)
return result
}
}
Swift details worth a closer look:
- Properties and methods.
resultis a stored property of the class. Methods read and write it directly, and Swift allows this in a class without marking methodsmutating, because classes are reference types. (A struct would needmutating.) - Method order. The helper methods may be declared in any order inside the class; a method can call one that appears later.
- Multi-line
&&chains. A line that ends with&&continues on the next line. The operator short-circuits: the firstfalseends the evaluation, so the remaining, more expensive checks are skipped. - Optionals. Every child is a
TreeNode?. Each method checksroot == nilfirst, which makesroot!safe afterwards. - Strict comparisons. The checks use
<and>, so equal values break the BST rule, as the statement defines it. - State in a property. Because
resultlives on the object, a second call on the sameSolutioninstance starts from the old value. After a call that returns 6, a later call on a tree whose true answer is 0 also returns 6. Create a newSolutionfor each tree, or resetresult.
Complexity
Let n be the number of nodes.
Time: much worse than linear. One call of isBST on a subtree of k nodes calls isBST on its children and also scans a child subtree with everythingLess or everythingGreater, so for a balanced tree it costs about k log k, and for a chain it costs about k². dfs calls it for every node. For a balanced tree the total is roughly O(n log² n). For the worst case, a chain such as a right-leaning tree with increasing values, the total is O(n³): doubling the chain length makes the work about eight times larger. That is fine for small trees but would be far too slow for a chain of 40,000 nodes, which the constraints allow.
Space: O(h). Only the recursion uses memory, as deep as the tree is tall.
Edge cases and common mistakes
- All negative values.
[-4, -2, -5]returns 0, becauseresultstarts at 0 and no positive sum replaces it. - A BST inside a larger tree. The best answer is often a deep subtree. For
[5, 4, 8, 3, null, 6, 3]the answer is 7, the subtree of node 4 with its child 3. The subtree of node 8 fails because its right child, 3, is not greater than 8, so the whole tree fails too. - Checking only the children. A node can be larger than its left child and still be smaller than something deeper on the left. The full-subtree checks catch this.
- Equal values. A node with a child of the same value is not a BST under this definition.
- Forgetting to visit the children in
dfs. Then only the root would be tested. - Reusing the object. As noted above,
resultkeeps its value between calls.
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.
