Skip to content

Maximum Sum BST

When Postorder Carries More Than One Value

You saw pair-return in Chapter 3 — returning two values from a recursive call so the parent can make a decision without re-traversing children. This problem pushes that idea further. You need to return four pieces of information from each subtree, and the parent combines all of them in a single step.

Problem: Maximum Sum BST (LC 1373)

Problem: Given a binary tree, find the maximum sum of all keys of any subtree which is also a Binary Search Tree (BST). If no BST subtree exists, return 0.

A subtree must include all of its descendants. A single node is a valid BST.

        1
       / \
      4   3
     / \ / \
    2  4 2  5
           / \
          4   6

The subtree rooted at node 3 is not a BST (left child 2, right child 5, but 3 is a BST root — wait, is it?). The subtree rooted at node 5 with children 4 and 6 IS a valid BST with sum \(5 + 4 + 6 = 15\). The answer is 20 (the subtree rooted at 3: \(3 + 2 + 5 + 4 + 6 = 20\), which is a valid BST).

What Each Node Needs to Know

To decide whether a subtree rooted at node \(X\) is a valid BST, you need:

  1. Is the left subtree a BST? If not, \(X\)'s subtree can't be either.
  2. Is the right subtree a BST? Same reason.
  3. The maximum value in the left subtree. It must be less than \(X.val\) for BST property.
  4. The minimum value in the right subtree. It must be greater than \(X.val\).
  5. The sum of the left subtree and sum of the right subtree — so you can compute this subtree's total sum.

That's a lot of information. But it all flows upward in one pass. Each node returns a tuple: \(\{isBST, minVal, maxVal, subtreeSum\}\).

The pattern: Postorder with a multi-value return. Each node makes a local decision using only what its children reported. No re-traversal, no global state except the running maximum.

Each node returns a four-value tuple: isBST, min, max, and subtree sum

The Null Node Convention

What should a null node return? It should not break any BST check. A null left child should report a maximum value of \(-\infty\) (so that \(-\infty < node.val\) is always true). A null right child should report a minimum value of \(+\infty\) (so that \(+\infty > node.val\) is always true). Both are valid BSTs with sum 0.

So: \(\text{null} \to \{isBST: true, minVal: +\infty, maxVal: -\infty, sum: 0\}\).

This is the same trick as returning \(-1\) for height of null — pick the identity value that makes the parent's logic work without special cases.

Postorder trace propagates BST info upward, tracking the global maximum sum

Full Trace

        1
       / \
      4   3
     / \ / \
    2  4 2  5
           / \
          4   6

We process postorder (leaves first, root last). For brevity, using \(+\infty = 2 \times 10^9\) and \(-\infty = -2 \times 10^9\).

Node Left Info Right Info BST check isBST min max sum globalMax
2 (left of 4) null: {T, \(+\infty\), \(-\infty\), 0} null: {T, \(+\infty\), \(-\infty\), 0} T and T and \(-\infty < 2\) and \(+\infty > 2\) T 2 2 2 2
4 (right of 4) null null same as above T 4 4 4 4
4 (left of root) {T, 2, 2, 2} {T, 4, 4, 4} T and T and \(2 < 4\) and \(4 > 4\)? No (\(4 \not> 4\)) F 2 4 10 4
2 (left of 3) null null valid T 2 2 2 4
4 (left of 5) null null valid T 4 4 4 4
6 (right of 5) null null valid T 6 6 6 6
5 {T, 4, 4, 4} {T, 6, 6, 6} T and T and \(4 < 5\) and \(6 > 5\) T 4 6 15 15
3 {T, 2, 2, 2} {T, 4, 6, 15} T and T and \(2 < 3\) and \(4 > 3\) T 2 6 20 20
1 (root) {F, 2, 4, 10} {T, 2, 6, 20} F (left is not BST) F 1 6 31 20

Final answer: \(globalMax = 20\).

Manual verification: The subtree rooted at 3 has nodes \(\{2, 3, 4, 5, 6\}\). In-order: \(2, 3, 4, 5, 6\) — sorted, so it's a valid BST. Sum \(= 2 + 3 + 4 + 5 + 6 = 20\). Correct.

The Code

struct SubtreeInfo {
    bool isBST;
    int minVal;
    int maxVal;
    int subtreeSum;
};

SubtreeInfo solve(TreeNode* node, int& globalMaxSum) {
    if (!node) return {true, (int)2e9, (int)-2e9, 0};

    auto leftInfo = solve(node->left, globalMaxSum);
    auto rightInfo = solve(node->right, globalMaxSum);

    bool validBST = leftInfo.isBST && rightInfo.isBST
                    && leftInfo.maxVal < node->val
                    && rightInfo.minVal > node->val;

    int currentSum = leftInfo.subtreeSum + rightInfo.subtreeSum + node->val;

    if (validBST) {
        globalMaxSum = max(globalMaxSum, currentSum);
    }

    int currentMin = min(node->val, leftInfo.minVal);
    int currentMax = max(node->val, rightInfo.maxVal);

    return {validBST, currentMin, currentMax, currentSum};
}

int maxSumBST(TreeNode* root) {
    int globalMaxSum = 0;
    solve(root, globalMaxSum);
    return globalMaxSum;
}

Complexity: \(O(n)\) time (single postorder pass), \(O(h)\) space where \(h\) is the tree height.

Connection to Chapter 3

This is exactly the pair-return pattern from Chapter 3, scaled up. In diameter, you returned \(\{height\}\). In balanced check, you returned \(\{height, isBalanced\}\). Here you return \(\{isBST, minVal, maxVal, sum\}\) — four values, but the structure is identical. Each node collects child reports, makes a local decision, and passes its own report upward.

The number of values in the tuple doesn't change the pattern. What matters is: can each node answer its question using only what children report, without re-traversing? If yes, it's one postorder pass.

Try It

Input: root = [1,4,3,2,4,2,5,null,null,null,null,null,null,4,6]
Output: 20

Predict before running: What does the function return on a single node with value \(-5\)? That single node is a valid BST with sum \(-5\). But \(globalMaxSum\) starts at 0, and \(\max(0, -5) = 0\). So the answer is 0, not \(-5\). The problem asks for the maximum sum, and an empty subtree (sum 0) is implicitly allowed.

Challenge: What if the problem asked for the maximum sum BST subtree with at least 3 nodes? How would you modify the tuple?

Edge Cases to Watch For

  • All negative values and globalMaxSum initialization: globalMaxSum starts at 0, meaning an empty subtree (sum 0) is implicitly the answer. If the problem required at least one node, you would need to initialize globalMaxSum = INT_MIN instead. Read the problem statement carefully to determine which initialization is correct.
  • Duplicate values break BST validity: If a child has the same value as the parent (e.g., parent = 5, left child = 5), the BST check leftInfo.maxVal < node->val fails because \(5 \not< 5\). This uses strict inequality, which is correct for BSTs, but forgetting to use strict comparison would incorrectly accept equal values.

Problems

Problem Link Difficulty
LC 1373 --- Maximum Sum BST in Binary Tree leetcode.com/problems/maximum-sum-bst-in-binary-tree Hard
LC 98 --- Validate Binary Search Tree leetcode.com/problems/validate-binary-search-tree Medium
LC 333 --- Largest BST Subtree leetcode.com/problems/largest-bst-subtree Medium
LC 235 — LCA of BST leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree Medium
LC 538 — Convert BST to Greater Tree leetcode.com/problems/convert-bst-to-greater-tree Medium
LC 173 — BST Iterator leetcode.com/problems/binary-search-tree-iterator Medium

What's Next?

You've mastered tree structure and BST invariants. Now step back and see the bigger picture: trees aren't just a data structure. They're the hidden skeleton behind recursion, DP, backtracking, and the entire internet. Chapter 7 changes how you see algorithms.