Largest BST Subtree

medium tree dfs bst

Problem

Given the root of a binary tree, return the size of the largest subtree that is a Binary Search Tree.

Inputroot = [10,5,15,1,8,null,7]

Output3

BST subtree [5,1,8] of size 3 wins (the right subtree breaks BST order at 7 < 15).

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

def largest_bst_subtree(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:
            size = ls + rs + 1
            best = max(best, size)
            return (True, size, min(lmin, node.val), max(rmax, node.val))
        return (False, 0, 0, 0)
    dfs(root)
    return best

function largestBSTSubtree(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 size = ls + rs + 1;
      best = Math.max(best, size);
      return [true, size, 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 largestBSTSubtree(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 size = L[1] + R[1] + 1;
            best = Math.max(best, size);
            return new int[]{ 1, size, 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 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 size = ls + rs + 1;
            best = max(best, size);
            return {true, size, min(lmin, n->val), max(rmax, n->val)};
        }
        return {false, 0, 0, 0};
    }
public:
    int largestBSTSubtree(TreeNode* root) { dfs(root); return best; }
};

Explanation

To find the biggest subtree that is a valid BST, we let each subtree report a small summary up to its parent. We use a post-order DFS that returns four facts: is it a BST, its size, and its min and max values.

The merge rule is the heart of it. A node forms a BST only if both children are BSTs and the node's value fits strictly between them: left.max < node.val < right.min. That single check guarantees the whole subtree respects BST ordering.

When the check passes, the subtree's size is left.size + right.size + 1, and we bubble up new bounds min(left.min, node.val) and max(right.max, node.val). We also update a global best. If the check fails, we return a "not a BST" marker so any ancestor knows it cannot be a BST either.

Empty children return (True, 0, +∞, -∞) so a single leaf always satisfies +∞-style bounds and counts as a BST of size 1.

Example: root = [10,5,15,1,8,null,7]. The subtree at 5 with children 1 and 8 is a valid BST of size 3. The right side breaks because 7 < 15, so 15 is not a BST root. The answer is 3. Each node is processed once, giving O(n) time.

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