Maximum Sum BST in Binary Tree
Maximum Sum BST in Binary Tree is LeetCode 1373 (Hard). You are given the root of a binary tree that is not necessarily a binary search tree. Among all of its subtrees that are valid BSTs, return the largest sum of keys.
- A subtree means a node together with all of its descendants; you cannot cut branches off.
- A valid BST has every key in the left subtree strictly less than the node's key and every key in the right subtree strictly greater, and both subtrees are BSTs themselves. Duplicate keys therefore break the property.
- An empty tree counts as a BST with sum 0, so the answer is never negative.
- The number of nodes in the tree is in the range [1, 4 * 10⁴].
- -4 * 10⁴ <= Node.val <= 4 * 10⁴
Intuition
Testing every node separately walks each subtree again, which is O(n²) on a tall tree. Turn it around and let every node report upward instead.
To decide whether a node roots a BST, it needs only four facts about each child's subtree: is it a BST, its smallest key, its largest key, and its sum. Then left.max < node.val < right.min settles it in O(1), and the node reports its own four facts to its parent.
A post-order DFS produces these bottom-up in one pass, and every node that qualifies offers its sum as a candidate answer, even if an ancestor later fails.
When a question asks for the best subtree with some property, and the property of a node depends on facts about its children, return a small tuple from a post-order DFS. Here the tuple is (isBST, min, max, sum). Validate Binary Search Tree uses the same min/max reasoning top-down; Largest BST Subtree uses exactly this tuple with a node count instead of a sum.
Approach
Before reading on: for a node whose left child is 3 and right child is 7, is checking 3 < node < 7 enough to call it a BST? Build a small counterexample. Then decide what an empty child should report so a leaf passes the check.
Define what each call returns
dfs(node) returns (isBST, lo, hi, total): whether the subtree is a BST, its smallest and largest keys, and its sum.
Report the empty tree as a passing BST
dfs(None) returns (True, +∞, −∞, 0). With the infinities reversed, the parent's test left.hi < val < right.lo always holds on the empty side.
Combine the two children after visiting them
If both children are BSTs and left.hi < node.val < right.lo, the node roots a BST: its sum is left.total + right.total + node.val, its smallest key is min(left.lo, node.val) and its largest max(right.hi, node.val).
Record every BST's sum, and fail the rest
Update a global best whenever a node roots a BST, before returning. Otherwise return isBST = False; every ancestor then fails too, while the sums already recorded below it stay counted.
Maximum Sum BST in Binary Tree solution in Python | C++ | Java
best starts at 0, not −∞, because an empty subtree is a valid BST.best starts at 0, not −∞, because an empty subtree is a valid BST.best starts at 0, not −∞, because an empty subtree is a valid BST.best = 0 encodes. Starting at −∞ would have returned -2.Common pitfalls
Comparing with the children instead of the subtree extremes
if node.left.val < node.val < node.right.val:
if lb and rb and lhi < node.val < rlo:
The BST rule covers the whole subtree. Take root 5 with children 3 and 8, and 9 as the right child of 3. Both direct children look fine, but 9 sits on the left of 5. Only the left subtree's maximum (9) catches it.
Allowing equal keys
if lb and rb and lhi <= node.val <= rlo:
if lb and rb and lhi < node.val < rlo:
A BST here needs strictly smaller keys on the left and strictly larger on the right. With <=, the tree [5, 5, 5] counts as one BST and returns 15; the right answer is 5, a single leaf.
Starting the answer at negative infinity
best = float("-inf")best = 0
The empty tree is a BST with sum 0, so 0 is always reachable. When every key is negative, the -inf start returns the least negative single node instead of 0.
Edge cases
In [4, 3, null, 1, 2] no subtree above the leaves is a BST, yet the answer is 2. The sum is recorded in best the moment a node qualifies, so a failure higher up cannot erase it; returning only the root's result would lose it.
Complexity
Maximum Sum BST vs Largest BST Subtree
The two problems run the same post-order pass. They differ in what a qualifying subtree is worth, and that changes the floor of the answer.
| Problem | Score of a BST subtree | Smallest possible answer |
|---|---|---|
| Maximum Sum BST in Binary Tree (LeetCode 1373) | sum of its keys (can be negative) | 0, the empty tree |
| Largest BST Subtree (LeetCode 333) | number of nodes | 1, any single node |
Maximum Sum BST in Binary Tree FAQ
Why does an empty subtree return +∞ as its minimum and −∞ as its maximum?
The parent checks left.max < val < right.min. A missing child must never make that check fail, so it reports the most permissive bounds: nothing is below −∞ or above +∞. The combined min and max then come out right too, because min(+∞, val) is val.
Can you walk through a maximum sum bst in binary tree example?
In LeetCode's first example the root 1 and its left child 4 are not BSTs (4 has a right child equal to 4). The right child 3 has children 2 and 5, and 5 has children 4 and 6. Those form a BST whose keys sum to 3 + 2 + 5 + 4 + 6 = 20, the answer.