DSA Tracker

Problem

Hard

Largest BST Subtree

A hard BST interview guide. Task statement, worked examples, intuition, and step-by-step solutions.

Topic
BST
Sheets
2
Core for
2 roles
PracticeWatch it step by step

The problem

Look at every subtree of a binary tree (a node together with everything below it) and find the biggest one that is a valid binary search tree. Return how many nodes it has.

Example 1

Input
root=[10,5,15,1,8,null,7]
Output
3
Why
The subtree rooted at node 5 with nodes 1, 5, and 8 is the largest BST with 3 nodes. The subtree at 15 is not a BST because 7 < 15 but is on the right.

Example 2

Input
root=[10,5,15,null,null,6,20]
Output
3
Why
The subtree rooted at node 15 with nodes 6, 15, and 20 is a valid BST with 3 nodes.

Example 3

Input
root=[1]
Output
1
Why
A single node is itself a BST of size 1.

Constraints

  • The number of nodes is in the range [1, 104].
  • -104 <= Node.val <= 104

How to think about it

Updated 2026-09-29

Checking whether each subtree is a BST from top to bottom recalculates properties repeatedly. Working bottom-up via postorder traversal solves it cleanly: a node forms a valid BST if both its left and right subtrees are valid BSTs, its value is strictly greater than the maximum in its left subtree, and strictly less than the minimum in its right subtree.

Approaches, worst first

  1. Top-down validation and counting

    time O(n^2) · space O(h)

    For every node, call a helper to test if the subtree rooted there is a valid BST. If valid, count its nodes; if not, recursively check its children. Re-checks the same subtrees multiple times, leading to quadratic runtime on unbalanced trees.

  2. Bottom-up postorder synthesisWrite this one

    time O(n) · space O(h)

    Traverse postorder returning a tuple for each subtree: `(isBST, size, minVal, maxVal)`. If both children are BSTs and `leftMax < node.val < rightMin`, merge them into a valid BST of size `leftSize + rightSize + 1`. Otherwise, return the maximum BST size found so far.

Where people lose marks · 2
  • Base case return values for null children: an empty subtree must return `minVal = infinity` and `maxVal = -infinity` so parent comparisons `leftMax < node.val < rightMin` evaluate correctly.
  • Confusing subtree with sub-graph: the BST must include all descendants of the selected node, not an arbitrary pruned subset.

Full solution

C++
#include <bits/stdc++.h>
using namespace std;

struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} };

struct Info {
    bool is_bst;
    int size;
    long long mn;
    long long mx;
};

static Info dfs(TreeNode* node, int& max_size) {
    if (!node) return {true, 0, LLONG_MAX, LLONG_MIN};
    Info l = dfs(node->left, max_size);
    Info r = dfs(node->right, max_size);
    if (l.is_bst && r.is_bst && l.mx < node->val && node->val < r.mn) {
        int sz = l.size + r.size + 1;
        max_size = max(max_size, sz);
        return {true, sz, min((long long)node->val, l.mn), max((long long)node->val, r.mx)};
    }
    return {false, 0, 0, 0};
}

int largestBst(TreeNode* root) {
    int max_size = 0;
    dfs(root, max_size);
    return max_size;
}
Java
import java.util.*;

public class Main {
    static class TreeNode { int val; TreeNode left, right; TreeNode(int x) { val = x; } }

    static class Info {
        boolean isBst;
        int size;
        long min;
        long max;
        Info(boolean isBst, int size, long min, long max) {
            this.isBst = isBst;
            this.size = size;
            this.min = min;
            this.max = max;
        }
    }

    static int maxSize = 0;

    static Info dfs(TreeNode node) {
        if (node == null) return new Info(true, 0, Long.MAX_VALUE, Long.MIN_VALUE);
        Info l = dfs(node.left);
        Info r = dfs(node.right);
        if (l.isBst && r.isBst && l.max < node.val && node.val < r.min) {
            int sz = l.size + r.size + 1;
            maxSize = Math.max(maxSize, sz);
            return new Info(true, sz, Math.min(node.val, l.min), Math.max(node.val, r.max));
        }
        return new Info(false, 0, 0, 0);
    }

    static int largestBst(TreeNode root) {
        maxSize = 0;
        dfs(root);
        return maxSize;
    }
}
Python
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def largest_bst(root):
    max_size = 0
    def dfs(node):
        nonlocal max_size
        if not node:
            return True, 0, float('inf'), float('-inf')
        l_bst, l_sz, l_min, l_max = dfs(node.left)
        r_bst, r_sz, r_min, r_max = dfs(node.right)
        if l_bst and r_bst and l_max < node.val < r_min:
            sz = l_sz + r_sz + 1
            max_size = max(max_size, sz)
            return True, sz, min(l_min, node.val), max(r_max, node.val)
        return False, 0, 0, 0
    dfs(root)
    return max_size
JavaScript
function TreeNode(val, left, right) {
    this.val = val;
    this.left = left || null;
    this.right = right || null;
}

function largestBst(root) {
    let maxSize = 0;
    function dfs(node) {
        if (!node) return { isBst: true, size: 0, min: Infinity, max: -Infinity };
        const left = dfs(node.left);
        const right = dfs(node.right);
        if (left.isBst && right.isBst && left.max < node.val && node.val < right.min) {
            const sz = left.size + right.size + 1;
            if (sz > maxSize) maxSize = sz;
            return {
                isBst: true,
                size: sz,
                min: Math.min(left.min, node.val),
                max: Math.max(right.max, node.val),
            };
        }
        return { isBst: false, size: 0, min: 0, max: 0 };
    }
    dfs(root);
    return maxSize;
}
Try it in the editor

The theory behind it

BST — the ground this problem stands on. All BST problems

What BST is

A binary search tree is a binary tree that enforces a strict ordering rule at every node. Every value stored in a node's left branch must be smaller than the node itself, and every value in its right branch must be larger. Because this rule holds true everywhere down the tree, searching for a value does not require checking every branch. At each step, a single comparison lets you discard an entire half of the remaining nodes.

When to reach for it

Reach for a binary search tree when problems mention sorted tree structures, finding the kth smallest element, checking tree validity, or searching within a range of values. Signals include queries for the next greater element in a dynamic set, finding the lowest common ancestor in a sorted tree, or converting sorted arrays into height-balanced trees. When data must remain sorted while supporting continuous insertions and lookups, BST properties are the target.

How the pattern works

Use the ordering property to prune entire subtrees. When looking for a key, move left if the target is smaller than the current node, or move right if it is larger, stopping when values match or when reaching a null link. For validating a tree, do not merely compare a node to its immediate children; pass valid lower and upper value bounds down through recursive calls. Walking a valid binary search tree in-order visits all values in strictly increasing numerical order.

More BST problems

Unique Binary Search TreesMediumUnique Binary Search Trees IIMediumValidate Binary Search TreeMediumLowest Common Ancestor of a Binary Search TreeMediumKth Smallest Element in a BSTMediumBinary Search Tree to Greater Sum TreeMediumDelete Node in a BSTMediumInsert into a Binary Search TreeMedium

Interactive Practice

PracticeWatch step-by-step visualizer

Target Roles

Core requirement for 2 roles:

SDE / Software EngineerDatabase Engineer

Asked at

AmazonD-E-ShawFlipkartMicrosoftSamsung

Track in your role's order

Pick your target role and all 370 problems resequence to what that interview actually asks.

Start free

Problem set and role mapping as of .