Maximum Sum BST in Binary Tree — LC 1373 Post-Order Metadata

Problem Statement#

LeetCode 1373 — Maximum Sum BST in Binary Tree | Difficulty: Hard

Given a binary tree root, return the maximum sum of all keys of any sub-tree which is also a Binary Search Tree. If no subtree qualifies, return 0. A BST requires all left descendants to be less than the node and all right descendants to be greater.

Constraints:

• The number of nodes is in the range [1, 40000]
• -4 * 10^4 <= Node.val <= 4 * 10^4

Input:  root = [1,4,3,2,4,2,5,null,null,null,null,null,null,4,6]
Output: 20
Explanation: The subtree rooted at 3 is a BST with sum 20.

Input:  root = [4,3,null,1,2]
Output: 2
Explanation: The subtree rooted at 2 is a BST with sum 2.

Why This Problem Matters#

Maximum Sum BST is a hard interview problem at Amazon and Google because it requires simultaneously validating BST properties while computing aggregate values — two tasks that must be done in a single bottom-up pass to achieve O(n) time. The naive approach (validate BST for every subtree separately) is O(n^2).

The key insight — propagating (min, max, sum) metadata upward — is a fundamental tree DP pattern. You see the same technique in problems like "count BST nodes in range," "validate BST," and "find the largest BST subtree (LC 333)." Mastering this metadata-propagation approach lets you solve a whole family of "compute something about every subtree efficiently" problems.

The Core Insight#

For each subtree, the DFS returns a 4-tuple: (is_bst, subtree_min, subtree_max, subtree_sum).

A node's subtree is a BST if and only if:

1. Both left and right subtrees are BSTs
2. left_max < node.val (all left values are smaller)
3. node.val < right_min (all right values are larger)

If valid: sum = left_sum + right_sum + node.val, update global max.

Null nodes return: (True, +infinity, -infinity, 0) — a null subtree is always a valid BST, and the extreme min/max values ensure any real node passes the BST check against a null child.

Visual Dry Run#

Subtree [3, 2, 5, null, null, 4, 6]:

Max sum = 20.

Solution (Optimal)#

class Solution:
    def maxSumBST(self, root) -> int:
        self.max_sum = 0
 
        def dfs(node):
            # Null: valid BST, neutral min/max, zero sum
            if not node:
                return True, float('inf'), float('-inf'), 0
 
            lb, l_min, l_max, l_sum = dfs(node.left)
            rb, r_min, r_max, r_sum = dfs(node.right)
 
            # Check BST property
            if lb and rb and l_max < node.val < r_min:
                total = l_sum + r_sum + node.val
                self.max_sum = max(self.max_sum, total)
                return True, min(l_min, node.val), max(r_max, node.val), total
 
            # Not a BST — propagate failure
            return False, 0, 0, 0
 
        dfs(root)
        return self.max_sum

var maxSumBST = function(root) {
    let maxSum = 0;
 
    function dfs(node) {
        if (!node) return [true, Infinity, -Infinity, 0];
 
        const [lb, lMin, lMax, lSum] = dfs(node.left);
        const [rb, rMin, rMax, rSum] = dfs(node.right);
 
        if (lb && rb && lMax < node.val && node.val < rMin) {
            const total = lSum + rSum + node.val;
            maxSum = Math.max(maxSum, total);
            return [true, Math.min(lMin, node.val), Math.max(rMax, node.val), total];
        }
 
        return [false, 0, 0, 0];
    }
 
    dfs(root);
    return maxSum;
};

Time: O(n) — each node visited exactly once Space: O(h) — recursion stack depth

Common Mistakes#

• Using <= instead of strict < in BST checks — standard BSTs require strict inequality
• Null nodes returning (True, 0, 0, 0) — the min/max must be extreme values (infinity/-infinity) so any node value passes the BST check against a null child
• Forgetting to propagate False upward when a subtree is not a BST — if you continue updating the global max with invalid subtrees, the answer will be wrong
• Checking only l_max < node.val and node.val < r_min without also verifying lb and rb — parent can only be a BST if children are BSTs too

Interview Tips#

• Name the 4-tuple explicitly: (is_bst, subtree_min, subtree_max, subtree_sum) before writing code
• Explain why null nodes return (True, +inf, -inf, 0) — this is the subtle correctness requirement
• Mention the connection to LC 333 (Largest BST Subtree) which tracks size instead of sum
• Start with the BST validation insight: strict inequalities between all descendants, not just direct children

Follow-up Questions#

• How would you find the largest BST subtree (by count, not sum)? Same approach — return (is_bst, min, max, count) instead of sum.
• What if the tree has duplicate values? Standard BST disallows duplicates with strict inequality. You could allow left-equal or right-equal by relaxing one side.
• How does this differ from LC 98 (Validate BST)? LC 98 validates the entire tree; this problem finds the maximum-sum valid BST subtree within a potentially invalid tree.
• Can you solve this iteratively? Yes, with an explicit stack and post-order traversal, but the recursive version is much cleaner.

Key Takeaways#

• Post-order DFS returns a 4-tuple: (is_bst, subtree_min, subtree_max, subtree_sum) for each node
• Null nodes return (True, +infinity, -infinity, 0) — neutral values that never falsely invalidate BST checks
• BST validity requires: left subtree is BST, right subtree is BST, left_max < node.val, node.val < right_min
• Update the global max sum whenever a valid BST subtree is found
• Once a subtree is not a BST, propagate (False, 0, 0, 0) upward — no ancestor can include it in a valid BST
• Time O(n), space O(h) — single pass is optimal
• The metadata-propagation pattern (returning multiple values from DFS) is reusable for any "compute subtree property bottom-up" problem