Problem overview
The method MaxSumBST receives the root of a binary tree and returns the largest sum of keys over all subtrees that are also binary search trees. In a BST, every key in a node's left subtree is strictly less than the node's key, every key in its right subtree is strictly greater, and both subtrees are BSTs themselves. A subtree here means a node together with everything below it.
Some small examples:
[2, 1, 3]is itself a BST, so the answer is 2 + 1 + 3 = 6.[4, 3, null, 1, 2]: the node 3 has the child 2 on its right, which is less than 3, so the subtree at 3 is not a BST. The root isn't one either. The leaves are BSTs, and the best is the leaf 2, so the answer is 2.[-4, -2, -5]: every sum is negative, and the empty tree counts as a BST with sum 0, so the answer is 0.[5, 4, 8, 3, null, 6, 3]: the node 8 has a right child 3, which is not greater than 8, and the root is therefore not a BST either. The subtree at 4 with its child 3 is a BST with sum 7, which is the best.
Approach: ask the question at every node
This lesson's approach is the most direct one, and it splits the problem into small helpers that each do one job:
- Visit every node of the tree. Each node is the root of one subtree.
- For that subtree, decide whether it is a BST.
- If it is, compute its sum and keep the largest one seen.
To decide whether a subtree is a BST, the lesson checks the definition literally: both children's subtrees are BSTs, everything on the left is less than the node, and everything on the right is greater. The "everything" checks must look at the whole subtree, not only the direct children. Checking only the children misses a tree like [5, 3, 8, null, 7], where the node 7 is greater than its parent 3 but sits to the left of 5.
This is easy to write and read, but it repeats work: a node deep in the tree is examined again for every ancestor. In the worst case, a tree shaped like a chain, that adds up to O(n²) time. The second lesson on this problem removes the repetition by returning facts from the recursion.
Step by step
- Keep the best answer in a field. Declare
int resultin the class and set it to 0 in a public constructorSolution(). A field is visible to every method, so the search can update it. Starting at 0 also covers the empty BST. - Call the search.
MaxSumBSTcallsDfs(root)and returnsresult. - Declare
Dfsas apublic voidmethod taking aTreeNode root. - Stop at
null. An empty subtree needs no work, so use a barereturn. - Recurse first. Call
Dfsonroot.leftand onroot.rightso every subtree below this node is checked. - Test the current subtree with
IsBST(root), a helper written later. - Update the answer with
Math.Max(result, Sum(root))when the subtree is a BST. - Write
Sum. Fornullit returns 0. Otherwise it returnsroot.valplus the sums of both children. - Write
IsBST. An empty tree is a BST, sonullreturnstrue. - Combine four checks with
&&: the left subtree is a BST, the right subtree is a BST, everything on the left is less thanroot.val, and everything on the right is greater. - Write
EverythingLess(root, val). Fornullit returnstrue. Otherwiseroot.val < valmust hold, and the same must hold for both children with the sameval. - Write
EverythingGreater(root, val), its mirror image with the comparison reversed.
The solution in C#
class Solution {
int result;
public Solution() {
result = 0;
}
public int Sum(TreeNode root) {
if (root == null) {
return 0;
}
return root.val + Sum(root.left) + Sum(root.right);
}
public bool EverythingLess(TreeNode root, int val) {
if (root == null) {
return true;
}
return root.val < val &&
EverythingLess(root.left, val) &&
EverythingLess(root.right, val);
}
public bool EverythingGreater(TreeNode root, int val) {
if (root == null) {
return true;
}
return root.val > val &&
EverythingGreater(root.left, val) &&
EverythingGreater(root.right, val);
}
public bool IsBST(TreeNode root) {
if (root == null) {
return true;
}
return IsBST(root.left) &&
IsBST(root.right) &&
EverythingLess(root.left, root.val) &&
EverythingGreater(root.right, root.val);
}
public void Dfs(TreeNode root) {
if (root == null) {
return;
}
Dfs(root.left);
Dfs(root.right);
if (IsBST(root)) {
result = Math.Max(result, Sum(root));
}
}
public int MaxSumBST(TreeNode root) {
Dfs(root);
return result;
}
};
The C# points to notice:
- A field and a constructor.
int result;is an instance field. It starts at 0 anyway, because C# gives fields their default values, and the constructor sets it explicitly, which makes the intent visible. A newSolutionobject starts with a clean answer. - Short-circuit
&&. The checks inIsBSTand in the two helpers stop at the firstfalse, so a failing subtree stops being examined early. A long expression can be split across lines, as the solution does. - Strict comparisons. The BST rule uses
<and>, not<=and>=, so a subtree with two equal keys in the wrong places is not a BST. - Name
MaxSumBST. The uppercaseBSTin the method name is part of the lesson's API, so keep it exactly.
Complexity
Time: O(n²) in the worst case. Dfs visits each of the n nodes. At each one, IsBST and Sum may walk the whole subtree below it. For a chain of n nodes, the subtree sizes are n, n - 1, ..., 1, which adds up to about n²/2 steps. For a balanced tree the total is closer to O(n log n).
Space: O(h) for the recursion, where h is the height. A chain of 40,000 nodes makes the recursion that deep.
Edge cases and common mistakes
- All keys negative. Starting
resultat 0 returns 0, the empty BST, as the third example expects. Starting atint.MinValuewould return a negative number. - Checking only the direct children. A key deep in the left subtree can still be larger than the node. That is why
EverythingLessandEverythingGreaterwalk the whole subtree. - Equal keys. A node with a child holding the same key is not a BST under this definition.
- A BST inside a non-BST. The root may fail while a deep subtree succeeds, so
Dfskeeps going after a failed check and tests every node. - Forgetting the base case in a helper. Each of the four recursive helpers needs a
nullcheck, with the right answer: 0 forSumandtruefor the three checks.
Testing
[2, 1, 3]gives 6.[4, 3, null, 1, 2]gives 2.[-4, -2, -5]gives 0.[5, 4, 8, 3, null, 6, 3]gives 7.[1, 4, 3, 2, 4, 2, 5, null, null, null, null, null, null, 4, 6]gives 20, from the subtree rooted at 3.