Maximum Sum BST in Binary Tree

Maximum Sum BST in Binary Tree is a classic tree problem that teaches the most important trick for tree questions: have each node return a small bundle of facts to its parent, so the whole tree is solved in one bottom-up pass.

The slow way first

The obvious idea: for every node, check whether its subtree is a BST, and if so add up its keys. But checking "is this subtree a BST" is itself an O(n) walk, and we would repeat it at every node — that is O(n²) overall, and it throws away work we already did lower in the tree.

The question to ask: while I am at a node, what do I wish my children had already told me? I wish each child had handed me four facts about its subtree: is it a BST, what is its smallest key, its largest key, and its total sum. With those, I can decide everything about the current node in O(1).

The idea: each node returns (isBST, min, max, sum)

Do a single post-order DFS (children first, then the node). Each call returns a 4-tuple:

• isBST — is this whole subtree a valid BST?
• min, max — the smallest and largest key in the subtree.
• sum — the total of all keys.

A node forms a BST exactly when both children are BSTs and left.max < node.val < right.min. When that holds, its sum is left.sum + node.val + right.sum, and we update a running best.

The key insight: a null child returns (True, +inf, -inf, 0). Those infinities make the comparison left.max < val and val < right.min automatically pass for a leaf, so leaves are handled with no special case.

Walk through it

Step through the animation. We go bottom-up. Leaves 2 and 6 are trivial BSTs, so best climbs to 6. Their parent 4 passes 2 < 4 < 6, forming a BST of sum 12 — a new best. The right subtree rooted at 3 also passes (2 < 3 < 7) and ties at 12. Finally the root 1 fails: its left subtree max is 6, and 6 < 1 is false, so the whole tree is not a BST. The answer stays 12.

Pseudocode

best = 0
function dfs(node):
    if node is null:
        return (True, +infinity, -infinity, 0)   # so leaves pass cleanly
    (lb, lmin, lmax, lsum) = dfs(node.left)
    (rb, rmin, rmax, rsum) = dfs(node.right)
    if lb and rb and lmax < node.val < rmin:
        total = lsum + node.val + rsum
        best = max(best, total)
        return (True, min(lmin, node.val), max(rmax, node.val), total)
    return (False, 0, 0, 0)                        # not a BST
dfs(root)
return best

The Python solution

def max_sum_bst(root):
    best = 0
    def dfs(node):
        if not node:
            return (True, inf, -inf, 0)
        nonlocal best
        lb, lmin, lmax, lsum = dfs(node.left)
        rb, rmin, rmax, rsum = dfs(node.right)
        if lb and rb and lmax < node.val < rmin:
            total = lsum + node.val + rsum
            best = max(best, total)
            lo = min(lmin, node.val)
            return (True, lo, max(rmax, node.val), total)
        return (False, 0, 0, 0)
    dfs(root)
    return best

• best holds the largest valid-BST sum seen so far; nonlocal lets the inner dfs update it.
• A null child returns (True, inf, -inf, 0) — the infinities make a leaf pass the BST test for free.
• We recurse into both children first (post-order), then combine their reports.
• Line 9 is the heart: both subtrees must be BSTs and left.max < node.val < right.min.
• When valid, we compute total, update best, and return this subtree's true (min, max, sum).
• If the node fails the test we return (False, 0, 0, 0) — the False poisons every ancestor, since no parent of a non-BST can be a BST.

Complexity

We visit every node once and do O(1) work there, so the pass is O(n). The extra space is O(h) for the recursion stack, where h is the tree height. The win comes from making each node report just enough for its parent to decide instantly.

When this pattern shows up

Practice