Problem overview
The method maxSumBST receives the root of a binary tree, a TreeNode | null, and returns the largest sum of the keys of any subtree that is also a binary search tree (BST). A subtree here means a node together with everything below it. A BST must satisfy three rules: the left subtree holds only keys strictly less than the node's key, the right subtree holds only keys strictly greater, and both subtrees are BSTs themselves.
In the tree [2,1,3] the whole tree is a BST and its sum is 6. In [4,3,null,1,2] the root 4 has a left child 3 whose children are 1 and 2. The node 3 breaks the rule, since its right child 2 is smaller than it, so only the leaves 1 and 2 qualify as BSTs, and the best sum is 2. In [-4,-2,-5] every sum is negative, and the answer is 0: an empty BST is allowed, so the result never drops below 0.
Approach: test each subtree directly
The most direct plan follows the definition. Visit every node. For each one, ask: is the subtree rooted here a BST? If it is, compute its sum and keep the largest sum seen. Start the best at 0, which also takes care of the empty-BST case.
Each question breaks down into small recursive helpers:
sum(root)adds up a subtree.everythingLess(root, val)andeverythingGreater(root, val)check that every value in a subtree is below, or above, a bound.isBST(root)applies the three BST rules, using the first two helpers for the "all less" and "all greater" parts.dfs(root)walks the tree and runsisBSTandsumat every node.
The value of this approach is that every piece is easy to read and to check. Its cost is repeated work: isBST rescans a subtree for every ancestor that asks about it. The second lesson on this problem removes that rescanning by returning the minimum, maximum and sum from a single post-order pass. Start here to see the idea clearly, then make it faster.
Step by step
- Store the best answer in a field. Declare
resultas anumberin the class and set it to 0 in a constructor. Every method can then update it throughthis. - Call the walker and return the field.
maxSumBSTcallsthis.dfs(root)and returnsthis.result. - Declare
dfswith aTreeNode | nullparameter and no return value. - Stop at a missing node with a bare
return. - Recurse into both children so every subtree below the current node is checked.
- Ask
isBSTabout the current node. - If it is a BST, update
resultto the larger of its current value and the subtree's sum, usingMath.max. - Write
sum. An empty subtree returns 0, and otherwise the sum is the node's value plus the sums of both children. - Write
isBST. An empty tree is a valid BST, so returntrue. - Combine four checks with
&&: the left subtree is a BST, the right subtree is a BST, everything on the left is less than the node, and everything on the right is greater. - Write
everythingLess. An empty subtree returnstrue. Otherwise the node's value must be below the bound, and the recursion must hold for both children with the same bound. - Write
everythingGreateras the mirror image, with the comparison reversed.
The solution in TypeScript
class Solution {
result: number;
constructor() {
this.result = 0;
}
sum(root: TreeNode | null): number {
if (!root) {
return 0;
}
return root.val + this.sum(root.left) + this.sum(root.right);
}
everythingLess(root: TreeNode | null, val: number): boolean {
if (!root) {
return true;
}
return root.val < val &&
this.everythingLess(root.left, val) &&
this.everythingLess(root.right, val);
}
everythingGreater(root: TreeNode | null, val: number): boolean {
if (!root) {
return true;
}
return root.val > val &&
this.everythingGreater(root.left, val) &&
this.everythingGreater(root.right, val);
}
isBST(root: TreeNode | null): boolean {
if (!root) {
return true;
}
return this.isBST(root.left) &&
this.isBST(root.right) &&
this.everythingLess(root.left, root.val) &&
this.everythingGreater(root.right, root.val);
}
dfs(root: TreeNode | null): void {
if (!root) {
return;
}
this.dfs(root.left);
this.dfs(root.right);
if (this.isBST(root)) {
this.result = Math.max(this.result, this.sum(root));
}
}
maxSumBST(root: TreeNode | null): number {
this.dfs(root);
return this.result;
}
}
The TypeScript details worth a closer look:
- Declared fields. TypeScript requires
result: number;in the class body before the constructor can assignthis.result. The annotation exists only at compile time. - State on the object. The field lives as long as the
Solutionobject does. If one object were used for two trees, the second call would start from the first call's answer. A fresh object, or resetting the field, avoids that. - Short-circuit
&&. Evaluation stops at the firstfalse, so once one check fails, the remaining ones don't run. For booleans,&&chains give back a boolean. - The line break after
return. Each expression starts on the same line asreturnand continues on lines that end with&&. A barereturnfollowed by a line break returnsundefined, because JavaScript inserts a semicolon there. - Narrowing. After
if (!root) return, the compiler treatsrootas aTreeNode, soroot.valandroot.leftare accepted.
Complexity
Let n be the number of nodes.
Time: heavy in the worst case. For a subtree of size s, isBST does work proportional to s at every node it recurses through, since each of those nodes also calls everythingLess or everythingGreater on its own subtrees. For a chain-shaped tree, that is O(s²) for a single isBST call, and dfs makes one such call for every node, which adds up to O(n³). In a test with chains of 100, 200 and 400 nodes, doubling the size made the running time roughly eight times longer. A balanced tree costs far less, because its subtrees are small. This is the price of the simple structure, and the next lesson's single pass brings it down to O(n).
Space: O(h). Only the recursion uses memory, one call per level of the tree, where h is the height.
Edge cases and common mistakes
- All values negative. The answer is 0, not the largest negative sum. Starting
resultat 0 does this automatically. - Checking only the direct children. A node can be larger than its left child and still violate the rule because of a deeper node. In
[10,5,15,null,null,6,20], the node 15 has a left child 6, which is below 10: the whole tree is not a BST, even though 5 < 10 < 15. The best BST is the subtree at 15, with sum 41. - Allowing equal keys. Both comparisons are strict, so duplicates break the BST rule. A node 2 with a left child 2 is not a BST.
- Forgetting that a non-BST can contain BSTs. This is why
dfsalways recurses into both children, whether or not the current node passes. - Using the whole tree's sum. The sum added to
resultis the sum of the BST subtree at that node, not of the whole tree. - Reusing one object. Because
resultpersists, a second call on the sameSolutionobject can return a stale larger value.
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.[10,5,15,null,null,6,20]gives41.