Problem overview
The method maxSumBST receives the root of a binary tree. Some of its subtrees, a node together with everything below it, are binary search trees (BSTs). The method returns the largest sum of the values in such a subtree. In a BST, every value in the left subtree of a node is strictly less than the node's value, every value in the right subtree is strictly greater, and both subtrees are BSTs themselves.
If every BST subtree has a negative sum, the answer is 0, which stands for an empty BST. A few examples:
- The tree with root 2 and children 1 and 3 is a BST itself, with sum 6.
- The tree with root -4 and children -2 and -5 gives 0: the root isn't a BST because -2 is greater than -4, and each single node has a negative sum.
- The tree with root 4, left child 3 and 3's children 1 and 2 gives 2: the subtree rooted at 3 isn't a BST, since 2 is greater than 3. The best BST is the single node 2.
Approach: test every subtree separately
A tree has one subtree for every node, so there are only n candidates. The simple plan is to visit every node, decide whether the subtree below it is a BST, and if it is, compare its sum with the best sum so far. The best sum starts at 0, which covers the "empty BST" case.
Deciding if a subtree is a BST needs more than comparing a node with its two children. For a root with value 10, a left child 5, and 5's right child 15, each parent-child pair looks fine on the left side, but 15 sits in the left subtree of 10 and is larger than 10. So the check must compare the node with every value in each subtree. The solution has two helpers, everythingLess and everythingGreater, that walk a whole subtree and check it against a bound. isBST uses them at every node.
This lesson accepts the simplest correct approach, even though it repeats work. A second lesson on this problem removes the repetition by having each subtree report its minimum, maximum and sum to its parent.
Step by step
- Declare a field
resultas avarof typeIntinitialized to 0, abovemaxSumBST, so every method of the class can read and update the best answer. - In
maxSumBST, calldfs(root), then end withresult. - Declare
dfswith aTreeNodeparameter and result typeUnit. - Stop on
nullwith a barereturn. - Visit both children with
dfs(root.left)anddfs(root.right), so every subtree belowrootis checked. - Test this subtree with
if (isBST(root)). - Update the best sum:
result = math.max(result, sum(root)). Startingresultat 0 means that when every BST sum is negative, 0 wins. - Write
sum: return 0 fornull, otherwiseroot.value + sum(root.left) + sum(root.right). - Write
isBST: an empty tree is a BST, so returntruefornull. Otherwise it is a BST when both children are BSTs, everything in the left subtree is less thanroot.value, and everything in the right subtree is greater. - Write
everythingLess(root, value):truefornull, otherwiseroot.value < valueand the same check holds for both children with the same bound. - Write
everythingGreater(root, value)the same way with the comparison reversed.
The solution in Scala
class Solution {
var result: Int = 0
def sum(root: TreeNode): Int = {
if (root == null) {
return 0
}
root.value + sum(root.left) + sum(root.right)
}
def everythingLess(root: TreeNode, value: Int): Boolean = {
if (root == null) {
return true
}
root.value < value &&
everythingLess(root.left, value) &&
everythingLess(root.right, value)
}
def everythingGreater(root: TreeNode, value: Int): Boolean = {
if (root == null) {
return true
}
root.value > value &&
everythingGreater(root.left, value) &&
everythingGreater(root.right, value)
}
def isBST(root: TreeNode): Boolean = {
if (root == null) {
return true
}
isBST(root.left) &&
isBST(root.right) &&
everythingLess(root.left, root.value) &&
everythingGreater(root.right, root.value)
}
def dfs(root: TreeNode): Unit = {
if (root == null) {
return
}
dfs(root.left)
dfs(root.right)
if (isBST(root)) {
result = math.max(result, sum(root))
}
}
def maxSumBST(root: TreeNode): Int = {
dfs(root)
result
}
}
Scala details:
- A line ending in
&&continues. A line that ends with an operator such as&&cannot be a complete expression, so the compiler reads the next line as its continuation. That is why the last line of each chain has no operator after it. &&short-circuits. It stops at the firstfalseoperand, so the remaining checks are skipped once one fails.- The last expression is the result. The boolean chain and
root.value + ...need noreturn. The earlyreturnlines fornullare ordinary and sit at the method's own level. - The parameter name
value.valis a Scala keyword, so the bound is calledvalue, the same as the field in the node class. - A field with
var.resultbelongs to the object, not to a call. It keeps its value between calls on the sameSolutionobject: if one object were used for two trees, the second answer could not be smaller than the first. A fresh object starts at 0. - Unit.
dfsreturnsUnitand works through side effects: it updatesresult.
Complexity
Time: more than linear. For one node, sum costs the size of its subtree. isBST costs more, because it runs everythingLess and everythingGreater at every level of the subtree. For a subtree of k nodes that is about k times its depth, so roughly k log k in a balanced tree. Adding this up for the n nodes of a balanced tree gives about O(n log^2 n). In a degenerate tree, where every node has one child, isBST costs O(k^2) for a subtree of k nodes, and the total over all nodes reaches O(n^3) when the whole chain is a BST. Failing checks stop early, which helps on many inputs. The approach is simple, but it is not the fast one.
Space: O(h), where h is the height of the tree, for the recursion. Each helper recurses to the depth of the subtree it examines.
Edge cases and common mistakes
- All values negative. The answer is 0, because
resultstarts at 0 and no negative sum can beat it. - Checking only direct children. The root 10 with a left child 5 whose right child is 15 passes a parent-child test everywhere, but it is not a BST. The best BST there is the subtree rooted at 5, with sum 20. This is why the helpers walk the whole subtree.
- Strict comparisons. Equal values break the rule. A root 2 with a single child 2 is not a BST, so the answer is 2, not 4. Using
<=in the helpers would accept it. - A non-BST parent over BST children. The subtree rooted at 5 in the tree 5, left 4 (child 3), right 8 (children 6 and 3) has two BST children on the left, but the whole thing isn't a BST. The answer there is 7, from the subtree 4 with child 3.
- Reusing a
Solutionobject. The fieldresultpersists, so a second call on the same object would start from the previous answer. - Only taking the root. The best BST is often deep inside the tree, which is why
dfstests every node.
Testing
- Root 1 with left child 4 (children 2, 4) and right child 3 (children 2, 5 where 5 has the children 4, 6): 20, from the subtree rooted at 3.
- Root 4 with left child 3 (children 1, 2): 2.
- Root -4 with children -2 and -5: 0.
- Root 2 with children 1 and 3: 6.
- Root 5 with left child 4 (child 3) and right child 8 (children 6 and 3): 7.
