Maximum Sum BST in Binary Tree

hard tree bst dfs

Problem

Given the root of a binary tree, find the largest possible sum of node values among all subtrees that are valid Binary Search Trees. A subtree is any node together with all of its descendants. A single node counts as a BST. If no subtree is a BST with a positive sum, the answer is 0.

Inputroot = [4, 3, 8, 1, 5]

Output9

The subtree rooted at 3 is a BST (1 < 3 < 5) with sum 1 + 3 + 5 = 9. The whole tree is not a BST because 8 sits to the right of 4 yet the left subtree's max is 5 > 4.

tree (level-order, 'n' for null)

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

function maxSumBST(root) {
  let best = 0;
  function dfs(node) {
    if (!node) return [true, 0, Infinity, -Infinity];
    const [lb, ls, lmin, lmax] = dfs(node.left);
    const [rb, rs, rmin, rmax] = dfs(node.right);
    if (lb && rb && lmax < node.val && node.val < rmin) {
      const total = ls + rs + node.val;
      best = Math.max(best, total);
      return [true, total, Math.min(lmin, node.val), Math.max(rmax, node.val)];
    }
    return [false, 0, 0, 0];
  }
  dfs(root);
  return best;
}

class Solution {
    int best = 0;
    public int maxSumBST(TreeNode root) { dfs(root); return best; }
    int[] dfs(TreeNode n) {
        if (n == null) return new int[]{ 1, 0, Integer.MAX_VALUE, Integer.MIN_VALUE };
        int[] L = dfs(n.left), R = dfs(n.right);
        if (L[0] == 1 && R[0] == 1 && L[3] < n.val && n.val < R[2]) {
            int total = L[1] + R[1] + n.val;
            best = Math.max(best, total);
            return new int[]{ 1, total, Math.min(L[2], n.val), Math.max(R[3], n.val) };
        }
        return new int[]{ 0, 0, 0, 0 };
    }
}

class Solution {
    int best = 0;
    tuple<bool,int,int,int> dfs(TreeNode* n) {
        if (!n) return {true, 0, INT_MAX, INT_MIN};
        auto [lb, ls, lmin, lmax] = dfs(n->left);
        auto [rb, rs, rmin, rmax] = dfs(n->right);
        if (lb && rb && lmax < n->val && n->val < rmin) {
            int total = ls + rs + n->val;
            best = max(best, total);
            return {true, total, min(lmin, n->val), max(rmax, n->val)};
        }
        return {false, 0, 0, 0};
    }
public:
    int maxSumBST(TreeNode* root) { dfs(root); return best; }
};

Explanation

We want the heaviest subtree that is still a valid Binary Search Tree. Checking every subtree from scratch would be slow, so instead each subtree reports a compact summary up to its parent. A single post-order DFS returns four facts about the subtree below a node: is it a BST, its sum, its minimum value, and its maximum value.

The merge rule is the key. A node forms a BST only when both of its children are BSTs and the node's value fits strictly between them: left.max < node.val < right.min. That one comparison is enough to guarantee the entire subtree obeys BST ordering, because the children already vouch for everything underneath them.

When the check passes, the subtree's sum is left.sum + right.sum + node.val, and we pass up tightened bounds min(left.min, node.val) and max(right.max, node.val). We also update a running best. When the check fails, we return a "not a BST" marker so any ancestor immediately knows it cannot be a BST either.

Empty children return (True, 0, +∞, -∞). Those infinities make a leaf trivially satisfy +∞-style bounds, so every leaf is a BST whose sum is just its own value. Because best starts at 0, trees whose only valid BSTs have negative sums correctly return 0.

Example: root = [4, 3, 8, 1, 5]. The node 3 with children 1 and 5 satisfies 1 < 3 < 5, giving a BST of sum 9. The root 4 fails because its left subtree's max is 5, which is not less than 4. The answer is 9. Each node is visited once, so the work is linear.

Time: O(n) Space: O(h)