Maximum Sum BST in Binary Tree
Find the maximum sum of keys of any subtree that is itself a valid BST.
Open on LeetCode ↗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.
One postorder pass returning a four-part summary per subtree: is it a BST, its min, its max, its sum. A node forms a BST only if both children do and its value sits strictly between the left max and the right min. Bundling everything a parent needs into one return value avoids repeated subtree scans.
Approach
Return a 4-tuple upward
(isBST, min, max, sum). Nulls report (True, +∞, −∞, 0) so leaves compose cleanly.
Combine at each node
Valid iff both children valid and leftMax < val < rightMin. New tuple: (True, min(leftMin,val), max(rightMax,val), sums+val).
Record candidates
Every valid combination updates the global best (empty subtree counts as 0 — answer never negative).
Solution & live demo
Common pitfalls
Validating each subtree independently
if isBST(node): best = max(best, sumTree(node))
lb, lmin, lmax, lsum = dfs(node.left)
Both helpers walk the whole subtree, so the total is O(n²) on a skewed tree. Returning the validity, bounds, and sum together means each node is visited once.
Comparing against the children's values instead of their extremes
if node.left.val < node.val < node.right.val:
if lb and rb and lmax < node.val < rmin:
The BST property constrains the entire subtree, not just the immediate children. A deep node in the left subtree may exceed the root while the direct child does not, and only the subtree maximum catches it.
Initialising the answer to negative infinity
self.best = float('-inf')self.best = 0
An empty subtree is a valid BST with sum 0, so 0 is always achievable and the answer is never negative. Starting at −∞ returns a negative sum when every BST in the tree has one.
Edge cases
Best BST may be empty → answer 0 per problem statement.
Invalidity propagates up, but the deep subtree's sum was already recorded.