Problem statement

Given the root of a binary tree, consider every subtree of it (a node together with all of its descendants). Return the largest sum of node values among the subtrees that are binary search trees.

A subtree is a binary search tree when, for every node in it:

• every value in the node's left subtree is strictly less than the node's value,
• every value in the node's right subtree is strictly greater than the node's value,
• and both of those subtrees are binary search trees themselves.

An empty subtree counts as a binary search tree with sum 0, so the answer is never negative.

Example 1

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 — values 2, 3, 4, 5, 6 — is a binary search tree with sum 20.

Example 2

Input: root = [4,3,null,1,2]
Output: 2
Explanation: 3 has 1 and 2 below it in the wrong order; the best binary search tree is the single node 2.

Example 3

Input: root = [-4,-2,-5]
Output: 0
Explanation: Every non-empty binary search tree here has a negative sum, so the empty one wins.

Constraints

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

Hints for Maximum Sum BST in Binary Tree

1. Hint 1

   Checking each subtree from scratch costs O(n) per node. What would a node need to know about its children to decide in O(1)?

2. Hint 2

   A node roots a binary search tree when both children do, the left child's maximum is below the node's value and the right child's minimum is above it.

3. Hint 3

   Return four facts from each subtree in post-order — is it a BST, its minimum, its maximum, its sum — with an empty subtree reporting (yes, +∞, −∞, 0).

How to solve Maximum Sum BST in Binary Tree

Whether a subtree is a binary search tree depends only on its two child subtrees being binary search trees and on how their extreme values compare with the root. So one post-order pass, carrying (is BST, min, max, sum) upward, decides every subtree in constant time.

Approach

1. Define info(node) returning (isBST, min, max, sum); an empty subtree returns (true, +∞, −∞, 0).
2. For a node, compute L = info(left) and R = info(right) first.
3. If L.isBST, R.isBST and L.max < node.val < R.min, the subtree is a BST: its sum is L.sum + R.sum + node.val; update the answer and return (true, min(L.min, val), max(R.max, val), sum).
4. Otherwise return (false, …) — no ancestor can be a BST either.
5. Start the answer at 0 (the empty subtree) and return it.

Why it works

A tree is a BST exactly when its subtrees are BSTs and every left value is below the root and every right value above it; within a BST the extreme values are its minimum and maximum, so comparing L.max and R.min with the root checks all of those inequalities at once. Using +∞/−∞ for an empty side makes the comparison pass automatically.

Complexity

• Time — O(n)
• Space — O(h) for the recursion

Pitfalls

• Comparing a node only with its direct children is not enough — a grandchild can break the order.
• The empty subtree makes the answer at least 0; do not return a negative sum.
• The order is strict: a duplicate value anywhere in a subtree stops it being a BST.
• Once a subtree is not a BST, no subtree containing it is — return early instead of computing bogus extremes.

Reference solution

Python

from typing import Optional

def maxSumBST(root: Optional[TreeNode]) -> int:
    best = [0]
    INF = float('inf')

    # (is BST, min, max, sum) of the subtree at node
    def info(node):
        if node is None:
            return True, INF, -INF, 0
        lb, lmin, lmax, lsum = info(node.left)
        rb, rmin, rmax, rsum = info(node.right)
        if lb and rb and lmax < node.val < rmin:
            total = lsum + rsum + node.val
            best[0] = max(best[0], total)
            return True, min(lmin, node.val), max(rmax, node.val), total
        return False, 0, 0, 0

    info(root)
    return best[0]

Java

public static int maxSumBST(TreeNode root) {
    int[] best = { 0 };
    bstInfo(root, best);
    return best[0];
}

// {is BST (1/0), min, max, sum} of the subtree at node
static int[] bstInfo(TreeNode node, int[] best) {
    if (node == null) return new int[] { 1, Integer.MAX_VALUE, Integer.MIN_VALUE, 0 };
    int[] l = bstInfo(node.left, best), r = bstInfo(node.right, best);
    if (l[0] == 1 && r[0] == 1 && l[2] < node.val && node.val < r[1]) {
        int total = l[3] + r[3] + node.val;
        best[0] = Math.max(best[0], total);
        return new int[] { 1, Math.min(l[1], node.val), Math.max(r[2], node.val), total };
    }
    return new int[] { 0, 0, 0, 0 };
}

C++

int maxSumBST(TreeNode* root) {
    int best = 0;
    // {is BST (1/0), min, max, sum} of the subtree at node
    function<array<int, 4>(TreeNode*)> info = [&](TreeNode* node) -> array<int, 4> {
        if (!node) return {1, INT_MAX, INT_MIN, 0};
        array<int, 4> l = info(node->left), r = info(node->right);
        if (l[0] && r[0] && l[2] < node->val && node->val < r[1]) {
            int total = l[3] + r[3] + node->val;
            best = max(best, total);
            return {1, min(l[1], node->val), max(r[2], node->val), total};
        }
        return {0, 0, 0, 0};
    };
    info(root);
    return best;
}

JavaScript

var maxSumBST = function(root) {
    var best = 0;
    // [is BST, min, max, sum] of the subtree at node
    var info = function(node) {
        if (node === null) return [true, Infinity, -Infinity, 0];
        var l = info(node.left), r = info(node.right);
        if (l[0] && r[0] && l[2] < node.val && node.val < r[1]) {
            var total = l[3] + r[3] + node.val;
            best = Math.max(best, total);
            return [true, Math.min(l[1], node.val), Math.max(r[2], node.val), total];
        }
        return [false, 0, 0, 0];
    };
    info(root);
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More dynamic programming problems

• Maximum Path Sum Between Two Leaves Hard
• Height of Binary Tree After Subtree Removal Queries Hard
• Recover a Tree From Preorder Traversal Hard
• Vertical Order Traversal of a Binary Tree Hard
• Binary Tree Cameras Hard
• Binary Tree Maximum Path Sum Hard