Maximum Sum BST in Binary Tree
Find the maximum sum of keys of any subtree that is itself a valid BST.
Open on LeetCode ↗02
Intuition
Post-order: each node needs to know, from each child, whether that subtree is a BST plus its min, max, and sum. The node is a BST root iff left is a BST with max < node < right's min. Track the best BST sum seen anywhere.
03
Approach
1
Return a 4-tuple upward
(isBST, min, max, sum). Nulls report (True, +∞, −∞, 0) so leaves compose cleanly.
2
Combine at each node
Valid iff both children valid and leftMax < val < rightMin. New tuple: (True, min(leftMin,val), max(rightMax,val), sums+val).
3
Record candidates
Every valid combination updates the global best (empty subtree counts as 0 — answer never negative).
04
Solution & live demo
python
▶1class Solution:
▶2 def maxSumBST(self, root):
▶3 self.best = 0
▶4 INF = float("inf")
▶5 def dfs(node):
▶6 if not node: return True, INF, -INF, 0
▶7 lb, lmin, lmax, lsum = dfs(node.left)
▶8 rb, rmin, rmax, rsum = dfs(node.right)
▶9 if lb and rb and lmax < node.val < rmin:
▶10 s = lsum + rsum + node.val
▶11 self.best = max(self.best, s)
▶12 return True, min(lmin, node.val), max(rmax, node.val), s
▶13 return False, 0, 0, 0
▶14 dfs(root)
▶15 return self.best
05
Edge cases
All negative keys
Best BST may be empty → answer 0 per problem statement.
Invalid parent, valid deep subtree
Invalidity propagates up, but the deep subtree's sum was already recorded.
06
Complexity
Time
O(n)
Space
O(h)
One post-order pass with tuples.