Largest BST Subtree

Description

A binary tree that isn't a BST can still contain subtrees that are. Checking every subtree from scratch repeats a lot of work. The fix is a bottom-up pass in which each subtree hands its parent a small summary: whether it's a BST, how big it is, and its smallest and largest values. With that, the parent can judge itself in O(1). This skill is about choosing that summary, and the same method answers related questions such as the highest-sum BST.

We'll go from simple to more technical:

1. The pattern: return (size, min, max) from each subtree, postorder.
2. A second flavor: rank by sum instead of size.
3. Where "largest valid region" questions show up.
4. What breaks it: local-only checks, re-validation, invalid that doesn't propagate, and sentinels.

The approach

int maxSize = 0;

int largestBSTSubtree(TreeNode root) {
    helper(root);
    return maxSize;
}

// returns {size, min, max}; size == -1 means "not a BST"
int[] helper(TreeNode node) {
    if (node == null) return new int[]{0, Integer.MAX_VALUE, Integer.MIN_VALUE};  // empty: a BST that blocks nothing
    int[] left = helper(node.left);
    int[] right = helper(node.right);
    if (left[0] != -1 && right[0] != -1 && node.val > left[2] && node.val < right[1]) {
        int size = left[0] + right[0] + 1;
        maxSize = Math.max(maxSize, size);
        return new int[]{size, Math.min(left[1], node.val), Math.max(right[2], node.val)};
    }
    return new int[]{-1, 0, 0};
}

def largest_bst_subtree(root: TreeNode | None) -> int:
    max_size = 0

    def helper(node: TreeNode | None) -> tuple:
        """(size, min, max); size == -1 means "not a BST"."""
        nonlocal max_size
        if node is None:
            return 0, float("inf"), float("-inf")     # empty: a BST that blocks nothing
        l_size, l_min, l_max = helper(node.left)
        r_size, r_min, r_max = helper(node.right)
        if l_size != -1 and r_size != -1 and l_max < node.val < r_min:
            size = l_size + r_size + 1
            max_size = max(max_size, size)
            return size, min(l_min, node.val), max(r_max, node.val)
        return -1, 0, 0

    helper(root)
    return max_size

A subtree is a BST exactly when both children are BSTs and the node's value lies strictly between the largest value on its left and the smallest on its right. The children's min and max give that in O(1). Comparing only with the direct children isn't enough - a value deep in the left subtree can still be larger than the node.

The empty subtree reports min = Integer.MAX_VALUE and max = Integer.MIN_VALUE, so any real value passes the check against it with no null branches - and Math.min(left[1], node.val) falls back to the node's own value when the left side is empty.

A second flavor: the highest-sum BST instead of the largest

Change what the summary carries and the same pass answers a different question. For "the largest sum of keys in any BST subtree", carry the subtree's sum instead of its size:

long best = Long.MIN_VALUE;    // not 0: with all-negative values, the answer is negative

// returns {isBST, sum, min, max}; bounds in long so no real int value can reach them
long[] summarize(TreeNode node) {
    if (node == null) return new long[]{1, 0, Long.MAX_VALUE, Long.MIN_VALUE};
    long[] l = summarize(node.left), r = summarize(node.right);
    if (l[0] == 1 && r[0] == 1 && l[3] < node.val && node.val < r[2]) {
        long sum = l[1] + r[1] + node.val;
        best = Math.max(best, sum);
        return new long[]{1, sum, Math.min(l[2], node.val), Math.max(r[3], node.val)};
    }
    return new long[]{0, 0, 0, 0};
}

def max_sum_bst(root: TreeNode | None) -> int:
    best = float("-inf")     # not 0: with all-negative values, the answer is negative

    def summarize(node: TreeNode | None) -> tuple:
        """(is_bst, sum, min, max)"""
        nonlocal best
        if node is None:
            return True, 0, float("inf"), float("-inf")
        l_ok, l_sum, l_min, l_max = summarize(node.left)
        r_ok, r_sum, r_min, r_max = summarize(node.right)
        if l_ok and r_ok and l_max < node.val < r_min:
            total = l_sum + r_sum + node.val
            best = max(best, total)
            return True, total, min(l_min, node.val), max(r_max, node.val)
        return False, 0, 0, 0

    summarize(root)
    return best

Two things change beyond the field. The biggest BST no longer wins automatically - negative keys can make a smaller BST inside it sum to more. And best can't start at 0: every single node is a BST, so with all-negative values the answer is the largest (least negative) node, and a 0 start would report a sum that no subtree has.

Where you'll see it

"Find the largest well-formed region inside a structure that may be partly malformed" - the biggest correctly ordered run in a corrupted index, the largest well-typed sub-expression in a syntax tree with errors - is this bottom-up summary shape: each piece reports validity plus just enough about itself for its parent to decide in O(1).

Which tool for which job?

Common mistakes

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. In [10, 5, 15, 1, 12, null, 20], why is the whole tree not a BST, and how does the summary catch it?

2. Why does the empty subtree return min = Integer.MAX_VALUE and max = Integer.MIN_VALUE, and when is that a problem?

3. For the highest-sum BST subtree, why must the running best start below 0?

Key takeaways

• Each subtree returns a summary - valid?, size or sum, min, max - and the parent decides its own validity in O(1).
• A node must lie strictly between its left subtree's max and its right subtree's min; comparing with direct children isn't enough.
• "Invalid" propagates: once a child isn't a BST, no ancestor can be.
• Empty-subtree sentinels only work while no real value can equal them; use long bounds when values span the int range.
• Swap the ranked field (size, sum) to answer related questions - and start the running best where the answer can actually be.