Problem statement

Given the root of a binary tree, return the number of nodes in its largest subtree that is a binary search tree.

A subtree here is a node together with all of its descendants. It is a binary search tree when, for every node in it, every value in the node's left subtree is strictly smaller and every value in its right subtree is strictly larger than the node's own value. A single node is always a BST of size 1.

Example 1

Input: root = [5,2,4,1,3]
Output: 3
Explanation: The whole tree is not a BST (4 sits right of 5). The subtree rooted at 2 — 1, 2, 3 — is, with 3 nodes.

Example 2

Input: root = [6,6,3,null,2,9,3,null,8,8,2]
Output: 2
Explanation: The largest subtree that is a BST is the one rooted at 2 with its right child 8: 2 nodes. Larger subtrees all break the ordering somewhere.

Example 3

Input: root = [10,5,15,1,8,null,7]
Output: 3
Explanation: 7 in the right subtree of 10 breaks the whole tree; the subtree 5, 1, 8 is a BST of 3 nodes.

Constraints

• 1 <= number of nodes <= 10^5
• 1 <= Node.val <= 10^5

Hints for Largest BST in a Binary Tree

1. Hint 1

   Testing every subtree separately costs O(n) each — O(n²) in total. Let each subtree report what its parent needs instead.

2. Hint 2

   A node's subtree is a BST exactly when both children's subtrees are BSTs, the left one's maximum is below the node and the right one's minimum is above it.

3. Hint 3

   Post-order: return (is it a BST, its size, its minimum, its maximum). An empty subtree is a BST of size 0 with minimum +∞ and maximum −∞, which makes the comparisons work at leaves.

How to solve Largest BST in a Binary Tree

Compute, bottom-up, for every subtree whether it is a BST together with its size and value range. A parent combines its children's answers in O(1), and the largest size seen on a valid subtree is the answer.

Approach

1. Define walk(node) returning (ok, size, lo, hi); for an empty subtree return (true, 0, +∞, −∞).
2. For a node, get L = walk(left) and R = walk(right).
3. If L.ok, R.ok, L.hi < node.val < R.lo: the subtree is a BST of size L.size + R.size + 1 with range min(L.lo, val) to max(R.hi, val); update the best size.
4. Otherwise return ok = false (the other fields no longer matter).
5. Return the best size found.

Why it works

The BST property for a whole subtree is equivalent to: both child subtrees are BSTs and the node separates them — everything left is below it (equivalently the left maximum is) and everything right is above it (the right minimum is). The returned range is exactly the subtree's minimum and maximum, so the parent's test is exact. A subtree that is not a BST makes every ancestor's subtree fail too, which ok = false propagates.

Complexity

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

Pitfalls

• Checking only each node against its two children accepts trees like 10 → (5 → right 12): a grandchild can break the ordering.
• Equal values are not allowed in a BST here — the comparisons are strict.
• The answer counts a subtree with all its descendants; a BST formed by dropping part of a subtree does not count.

Reference solution

Python

from typing import Optional

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

    def walk(node):
        if node is None:
            return True, 0, INF, -INF
        lok, ls, llo, lhi = walk(node.left)
        rok, rs, rlo, rhi = walk(node.right)
        if lok and rok and lhi < node.val < rlo:
            size = ls + rs + 1
            best[0] = max(best[0], size)
            return True, size, min(llo, node.val), max(rhi, node.val)
        return False, 0, 0, 0

    walk(root)
    return best[0]

Java

public static int largestBst(TreeNode root) {
    int[] best = new int[1];
    bstWalk(root, best);
    return best[0];
}

// { ok (1/0), size, min, max }
static int[] bstWalk(TreeNode node, int[] best) {
    if (node == null) return new int[] { 1, 0, Integer.MAX_VALUE, Integer.MIN_VALUE };
    int[] l = bstWalk(node.left, best), r = bstWalk(node.right, best);
    if (l[0] == 1 && r[0] == 1 && l[3] < node.val && node.val < r[2]) {
        int size = l[1] + r[1] + 1;
        best[0] = Math.max(best[0], size);
        return new int[] { 1, size, Math.min(l[2], node.val), Math.max(r[3], node.val) };
    }
    return new int[] { 0, 0, 0, 0 };
}

C++

struct BstInfo { bool ok; int size, lo, hi; };
static BstInfo bstWalk(TreeNode* node, int& best);

int largestBst(TreeNode* root) {
    int best = 0;
    bstWalk(root, best);
    return best;
}

static BstInfo bstWalk(TreeNode* node, int& best) {
    if (!node) return {true, 0, INT_MAX, INT_MIN};
    BstInfo l = bstWalk(node->left, best), r = bstWalk(node->right, best);
    if (l.ok && r.ok && l.hi < node->val && node->val < r.lo) {
        int size = l.size + r.size + 1;
        best = max(best, size);
        return {true, size, min(l.lo, node->val), max(r.hi, node->val)};
    }
    return {false, 0, 0, 0};
}

JavaScript

var largestBst = function(root) {
    var best = 0;
    var walk = function(node) {
        if (node === null) return [1, 0, Infinity, -Infinity];
        var L = walk(node.left), R = walk(node.right);
        if (L[0] && R[0] && L[3] < node.val && node.val < R[2]) {
            var size = L[1] + R[1] + 1;
            if (size > best) best = size;
            return [1, size, Math.min(L[2], node.val), Math.max(R[3], node.val)];
        }
        return [0, 0, 0, 0];
    };
    walk(root);
    return best;
};

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

More dynamic programming problems

• Operations on Tree Medium
• Throne Inheritance Medium
• Convert Sorted List to Binary Search Tree Medium
• Foldable Binary Tree Medium
• K-th Largest Perfect Subtree Size in Binary Tree Medium
• Duplicate Subtree in Binary Tree Medium