Maximum Sum BST in Binary Tree: Post-Order Validation

You are given the root of a binary tree. Each node has an integer value. Your goal is to find the subtree that is a valid binary search tree (BST) and has the maximum sum of all its node values. Return that maximum sum. If no valid BST subtree exists (which cannot happen, since every leaf is trivially a BST), return 0.

This is LeetCode 1373: Maximum Sum BST in Binary Tree. It combines two classic tree skills: validating whether a subtree is a BST, and computing subtree sums using post-order DFS.

Why this problem matters

Most BST problems test one skill at a time. Validate BST checks structure. Binary Tree Maximum Path Sum tracks sums with a global max. This problem forces you to do both simultaneously.

That is what makes it hard. You need to bubble up multiple pieces of information from each subtree (is it a valid BST? what are its min and max values? what is the sum?) and combine them at the parent. The pattern of returning a tuple of values from a post-order DFS is a powerful building block that shows up in many tree problems beyond this one.

If you can solve this cleanly, you have internalized the bottom-up aggregation pattern that separates medium-level tree skills from advanced ones.

The key insight

You cannot check BST validity top-down here, because you also need the subtree sum, which requires a bottom-up pass. The trick is to do everything bottom-up in a single post-order traversal.

At each node, the recursive function returns a tuple: (is_bst, min_value, max_value, subtree_sum).

• is_bst: whether this subtree is a valid BST
• min_value: the smallest value in this subtree
• max_value: the largest value in this subtree
• subtree_sum: the sum of all node values in this subtree

To check if the current node forms a valid BST with its children, you verify:

1. Both children are valid BSTs
2. The left subtree's maximum value is strictly less than the current node's value
3. The right subtree's minimum value is strictly greater than the current node's value

If all three hold, the subtree rooted at this node is a valid BST, and you update the global max with its sum. If any condition fails, you mark this subtree as invalid, and every ancestor will also be invalid.

The solution

def max_sum_bst(root):
    best = 0

    def dfs(node):
        nonlocal best
        if node is None:
            return (True, float("inf"), float("-inf"), 0)

        l_bst, l_min, l_max, l_sum = dfs(node.left)
        r_bst, r_min, r_max, r_sum = dfs(node.right)

        if l_bst and r_bst and l_max < node.val < r_min:
            total = l_sum + node.val + r_sum
            best = max(best, total)
            return (True, min(l_min, node.val), max(r_max, node.val), total)

        return (False, 0, 0, 0)

    dfs(root)
    return best

Let's walk through the logic:

• best = 0 initializes the global max. The problem guarantees the answer is at least 0 (you can always pick an empty subtree conceptually, though in practice every single leaf is a valid BST with a positive, negative, or zero sum).
• For a null node, we return (True, inf, -inf, 0). This is a clever base case: inf as the minimum means any parent value will be smaller (which is fine since null has no actual values). -inf as the maximum means any parent value will be larger. The sum is 0.
• l_max < node.val < r_min is the BST validation check. The left subtree's largest value must be strictly less than the current node, and the right subtree's smallest value must be strictly greater.
• If the subtree is a valid BST, we compute its total sum and check it against best. We return the updated min (smallest in the entire subtree), max (largest in the entire subtree), and sum.
• If the subtree is not a valid BST, we return (False, 0, 0, 0). The exact min, max, and sum values do not matter because any ancestor that sees False will also be invalid.

Visual walkthrough

Let's trace the post-order DFS on a simplified version of the tree. At each node, we compute the four-value tuple and decide whether the subtree is a valid BST.

The key moment is Step 4. At node 3, both children are valid BSTs, left_max (2) is less than 3, and right_min (5) is greater than 3. The subtree is a valid BST with sum 10. In Step 5, node 1 cannot form a valid BST because its left child's subtree (rooted at 4) already failed. The invalid flag propagates upward, and the root is skipped.

Complexity analysis

Time is O(n). Every node is visited exactly once. At each node you do O(1) work: compare min/max values, add sums, and check the BST condition.

Space is O(h) where h is the height of the tree. That is the recursion stack depth. For a balanced tree, h = log n. For a skewed tree, h = n.

The building blocks

This problem combines three reusable sub-patterns:

1. Post-order DFS with tuple returns. Instead of returning a single value from each recursive call, you return a tuple of aggregated information. The parent unpacks both children's tuples, combines them, and returns its own tuple. This pattern appears whenever you need multiple pieces of information flowing upward through a tree. The skeleton:

def dfs(node):
    if node is None:
        return BASE_TUPLE
    left_info = dfs(node.left)
    right_info = dfs(node.right)
    combined = COMBINE(node, left_info, right_info)
    UPDATE_GLOBAL(combined)
    return combined

2. Bottom-up BST validation via min/max propagation. Instead of passing bounds downward (like in Validate BST), you propagate min and max values upward. Each node checks whether its value sits between the left subtree's max and the right subtree's min. This approach naturally combines with sum computation because both flow in the same direction.

3. Global max tracking with post-order side effect. The same pattern from Binary Tree Maximum Path Sum: you maintain a global variable and update it at each node, but the return value to the parent is different from what you check globally. Here, you update best with the subtree sum only when the subtree is a valid BST, while returning the full tuple for the parent's use.

Edge cases

• All negative values: best starts at 0. If every valid BST subtree has a negative sum, the answer is 0. A single leaf with value -5 is a valid BST, but its sum (-5) does not beat 0.
• Single node: the tree is trivially a valid BST. The answer is max(0, root.val).
• Entire tree is a valid BST: the answer is the sum of all nodes (if positive). The root's subtree passes all BST checks, and its sum is the total.
• No subtree with positive sum is a valid BST: the answer is 0. The problem specifies returning 0 when no valid BST subtree has a positive sum.
• Duplicate values: a BST requires strict inequality. A subtree where a child equals the parent is not a valid BST. The check l_max < node.val < r_min handles this correctly with strict comparison.

From understanding to recall

You just traced through the post-order DFS and watched the four-value tuple flow from leaves to root. You saw how (True, inf, -inf, 0) as the null base case makes leaves work automatically. You understand why an invalid child poisons every ancestor above it.

But in an interview, will you remember to use inf and -inf in the null base case? Will you remember that the BST check uses strict inequality with l_max and r_min, not l_min and r_max? Will you remember that best starts at 0, not negative infinity?

Understanding fades. Recall is what you need under pressure. Spaced repetition locks the pattern in. You reconstruct the tuple return and the BST validation check from scratch, first after a day, then after three days, then a week. After a few rounds, the null base case trick and the three-condition BST check become automatic.

The bottom-up tuple pattern, BST min/max propagation, and global max tracking are three of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling them individually is far more effective than grinding random problems and hoping it sticks.

Related posts

• Binary Tree Maximum Path Sum - The same global-max-with-local-return pattern, but tracking path sums instead of BST validity. Solve this first to learn the post-order global state trick.
• Validate Binary Search Tree - The foundational BST validation problem. This one uses top-down range bounds, while Maximum Sum BST uses bottom-up min/max propagation.
• Convert Sorted Array to Binary Search Tree - A simpler BST construction problem that helps you internalize BST properties before tackling validation.