Largest BST Subtree

Largest BST Subtree is a classic tree-recursion problem. It teaches the single most useful tree trick: have each node return a summary of its subtree so a parent can decide things in O(1) — the post-order bottom-up pattern.

The slow way first

The obvious idea: for every node, grab its whole subtree, check whether that subtree is a valid BST, and if so count its nodes. Keep the biggest count. But "is this subtree a BST?" is itself an O(n) walk, and we run it from every one of the n nodes — that is O(n²).

The question to ask: while I am checking a parent, what do I wish I already knew about its children? I wish I already knew whether each child's subtree is a BST, and its value range. If the children hand that up to me, the parent's check becomes O(1).

The idea: let each node return a summary

Walk the tree in post-order (children before the node). Each call returns four facts about its subtree: size, min value, max value, and valid? (is it a BST). A node is a valid BST when both children are valid and left.max < node.val < right.min. If so, its size is left.size + right.size + 1; otherwise it is invalid and pollutes every ancestor.

The key insight: a single bottom-up pass replaces the repeated subtree scans. One traversal, O(1) work per node.

Walk through it

Step through the animation. Post-order dives to the leaves 1 and 8 first — each a trivial BST of size 1. At node 5, the test 1 < 5 < 8 holds, so 5 is a valid BST of size 3 and becomes the best. On the right, node 15 fails because its right child 7 is smaller than 15, and that invalidity climbs up to the root 10. The answer stays 3.

Pseudocode

best = 0
function visit(node):
    if node is empty:
        return size 0, min +inf, max -inf, valid true
    summarize the left child  -> ls, lmin, lmax, lok
    summarize the right child -> rs, rmin, rmax, rok
    if lok and rok and lmax < node.val < rmin:
        size = ls + rs + 1
        best = max(best, size)
        return size, min(lmin, node.val), max(rmax, node.val), valid true
    return size 0, valid false      # poisons all ancestors
visit(root)
return best

The Python solution

def largest_bst_subtree(root):
    best = 0
    def visit(node):
        nonlocal best
        if node is None:
            return 0, inf, -inf, True
        ls, lmin, lmax, lok = visit(node.left)
        rs, rmin, rmax, rok = visit(node.right)
        if lok and rok and lmax < node.val < rmin:
            size = ls + rs + 1
            best = max(best, size)
            return size, min(lmin, node.val), max(rmax, node.val), True
        return 0, -inf, inf, False
    visit(root)
    return best

• best is shared across all calls via nonlocal; it tracks the largest valid BST size seen so far.
• The empty-child base case returns inf as min and -inf as max so the range test always passes for a missing side.
• We summarize the left and right children first — that is what makes this post-order.
• Line 9 is the heart: both children valid and lmax < node.val < rmin means this whole subtree is a BST.
• A valid node returns its real size and widened range; an invalid one returns size 0 and valid = False, which makes every ancestor fail too.

Complexity

We visit each node once and do constant work, so it is O(n) time. The extra space is O(h) for the recursion stack, where h is the tree height. That bottom-up return a summary move is the core of countless tree problems.

When this pattern shows up

Practice