Largest BST in a Binary Tree

Last Updated : 13 Oct, 2025

Given the root of a binary tree, find the size of the largest subtree that is also a Binary Search Tree (BST).
Note: Size of a BST means the number of nodes in the BST.

Examples:

Input:

Output: 3
Explanation: The below subtree is the maximum size BST:

Input:

Output: 1
Explanation: All the leaf nodes (2 and 3) of size 1 are valid BST.

Try it on GfG Practice

Table of Content

[Naive Approach] Using Recursion - O(n^2) Time and O(n) Space
[Expected Approach] - Using Binary Search Tree Property - O(n) Time and O(n) Space

[Naive Approach] By Checking All Subtree - O(n^2) Time and O(n) Space

A binary tree is a BST if, for its every node, all values in its left subtree are less than the node’s value, and all values in its right subtree are greater. This property must hold for every subtree in the tree.

The idea is to recursively check each subtree of a binary tree to determine whether it is a valid BST or not. If it is valid, count the nodes in that subtree and keep track of the maximum size.

C++

//Driver Code Starts
#include <iostream>
#include<climits>
using namespace std;

// Node structure
class Node {
public:
    int data;
    Node *left;
    Node *right;
    
    Node(int x) {
        data = x;
        left = nullptr;
      	right = nullptr;
    }
};
//Driver Code Ends


// Funtion to validate bst
bool isValidBst(Node *root, int minValue, int maxValue) {
    if (!root)
        return true;
    if (root->data >= maxValue || root->data <= minValue)
        return false;
    return isValidBst(root->left, minValue, root->data) && 
           isValidBst(root->right, root->data, maxValue);
}

// Funtion to calculate size of subtree
int size(Node *root) {
    if (!root)
        return 0;
    return 1 + size(root->left) + size(root->right);
}

// Finds the size of the largest BST
int largestBst(Node *root) {
    if (!root)
        return 0;
    
    // Check Subtree is valid or not
    if (isValidBst(root, INT_MIN, INT_MAX)) 
        return size(root);
  
    // Recursively call for left and right child
    return max(largestBst(root->left), 
               largestBst(root->right));
}


//Driver Code Starts
int main() {
  
	// Constructed binary tree 
    //         5
    //       /   \
    //      2     4
    //     / \
    //    1   3

    Node *root = new Node(5);
    root->left = new Node(2);
    root->right = new Node(4);
    root->left->left = new Node(1);
    root->left->right = new Node(3);

    cout << largestBst(root) << endl;
    return 0;
}

//Driver Code Ends

Java

//Driver Code Starts

// Node structure
class Node {
    public int data;
    public Node left;
    public Node right;

    public Node(int x) {
        data = x;
        left = null;
        right = null;
    }
}

public class Main {
//Driver Code Ends

    
    // Function to validate BST
    public static boolean isValidBst(Node root, int minValue, int maxValue) {
        if (root == null)
            return true;
        if (root.data >= maxValue || root.data <= minValue)
            return false;
        return isValidBst(root.left, minValue, root.data) &&
               isValidBst(root.right, root.data, maxValue);
    }

    // Function to calculate size of subtree
    public static int size(Node root) {
        if (root == null)
            return 0;
        return 1 + size(root.left) + size(root.right);
    }

    // Finds the size of the largest BST
    public static int largestBst(Node root) {
        if (root == null)
            return 0;

        // Check Subtree is valid or not
        if (isValidBst(root, Integer.MIN_VALUE, Integer.MAX_VALUE))
            return size(root);

        // Recursively call for left and right child
        return Math.max(largestBst(root.left), largestBst(root.right));
    }


//Driver Code Starts
    public static void main(String[] args) {
        
        // Constructed binary tree
        //         5
        //       /   \
        //      2     4
        //     / \
        //    1   3

        Node root = new Node(5);
        root.left = new Node(2);
        root.right = new Node(4);
        root.left.left = new Node(1);
        root.left.right = new Node(3);

        System.out.println(largestBst(root));
    }
}
//Driver Code Ends

Python

#Driver Code Starts

# Node structure
class Node:
    def __init__(self, x):
        self.data = x
        self.left = None
        self.right = None
#Driver Code Ends


# Function to validate BST
def isValidBst(root, min_value, max_value):
    if not root:
        return True
    if root.data >= max_value or root.data <= min_value:
        return False
    return (isValidBst(root.left, min_value, root.data) and
            isValidBst(root.right, root.data, max_value))

# Function to calculate size of subtree
def size(root):
    if not root:
        return 0
    return 1 + size(root.left) + size(root.right)

# Finds the size of the largest BST
def largestBst(root):
    if not root:
        return 0

    # Check Subtree is valid or not
    if isValidBst(root, float('-inf'), float('inf')):
        return size(root)

    # Recursively call for left and right child
    return max(largestBst(root.left), largestBst(root.right))


#Driver Code Starts
if __name__ == '__main__':
    
    # Constructed binary tree
    #         5
    #       /   \
    #      2     4
    #     / \
    #    1   3

    root = Node(5)
    root.left = Node(2)
    root.right = Node(4)
    root.left.left = Node(1)
    root.left.right = Node(3)

    print(largestBst(root))
#Driver Code Ends

C#

//Driver Code Starts
using System;

// Node structure
public class Node {
    public int data { get; set; }
    public Node left { get; set; }
    public Node right { get; set; }

    public Node(int x) {
        data = x;
        left = null;
        right = null;
    }
}

public class GFG {
//Driver Code Ends

    
    // Function to validate BST
    public static bool isValidBst(Node root, int minValue, int maxValue) {
        if (root == null)
            return true;
        if (root.data >= maxValue || root.data <= minValue)
            return false;
        return isValidBst(root.left, minValue, root.data) &&
                isValidBst(root.right, root.data, maxValue);
    }

    // Function to calculate size of subtree
    public static int size(Node root) {
        if (root == null)
            return 0;
        return 1 + size(root.left) + size(root.right);
    }

    // Finds the size of the largest BST
    public static int largestBst(Node root) {
        if (root == null)
            return 0;

        // Check Subtree is valid or not
        if (isValidBst(root, int.MinValue, int.MaxValue))
            return size(root);

        // Recursively call for left and right child
        return Math.Max(largestBst(root.left), largestBst(root.right));
    }


//Driver Code Starts
    public static void Main() {
        
        // Constructed binary tree 
        //         5
        //       /   \
        //      2     4
        //     / \
        //    1   3

        Node root = new Node(5);
        root.left = new Node(2);
        root.right = new Node(4);
        root.left.left = new Node(1);
        root.left.right = new Node(3);

        Console.WriteLine(largestBst(root));
    }
}

//Driver Code Ends

JavaScript

//Driver Code Starts

// Node structure
class Node {
    constructor(x) {
        this.data = x;
        this.left = null;
        this.right = null;
    }
}
//Driver Code Ends


// Function to validate BST
function isValidBst(root, minValue, maxValue) {
    if (!root)
        return true;
    if (root.data >= maxValue || root.data <= minValue)
        return false;
    return isValidBst(root.left, minValue, root.data) &&
           isValidBst(root.right, root.data, maxValue);
}

// Function to calculate size of subtree
function size(root) {
    if (!root)
        return 0;
    return 1 + size(root.left) + size(root.right);
}

// Finds the size of the largest BST
function largestBst(root) {
    if (!root)
        return 0;

    // Check Subtree is valid or not
    if (isValidBst(root, Number.MIN_SAFE_INTEGER, Number.MAX_SAFE_INTEGER))
        return size(root);

    // Recursively call for left and right child
    return Math.max(largestBst(root.left), largestBst(root.right));
}


//Driver Code Starts
// Driver Code
// Constructed binary tree 
//         5
//       /   \
//      2     4
//     / \
//    1   3

const root = new Node(5);
root.left = new Node(2);
root.right = new Node(4);
root.left.left = new Node(1);
root.left.right = new Node(3);

console.log(largestBst(root));
//Driver Code Ends

Output

[Expected Approach] - Using Binary Search Tree Property - O(n) Time and O(n) Space

Intiution:

To determine if a subtree is a valid BST, we know that all values in the left subtree must be smaller than the root, and all values in the right subtree must be greater than the root. If we track the minimum and maximum values of each subtree, we can easily validate a Binary tree.

To keep track of this information and size of valid BST, we create a custom class with the following attributes:

mini = Minimum value in the subtree
maxi = Maximum value in the subtree
mxSz = Size of the largest BST in the subtree

This allows us to efficiently compute the largest BST while recursively traversing the binary tree.

Pseudo-code Idea

If the root is NULL, then return (mini = + Infinity , maxi = - Infinity , size = 0) because an empty tree is a valid BST of size 0. Otherwise, make a recursive call for the left and right subtrees to get their (mini, maxi, size) values.
If (left -> maxi) < root -> data (< right -> mini), then the current subtree is a valid BST. return min = min(left -> mini, root -> data), max = max(right -> maxi, root -> data) and size = 1 + left -> size + right -> size .
if this condition fails, it means the current subtree is not a valid BST. So, return (mini = - Infinity, maxi = + Infinity, size = max(left -> size, right -> size)).

C++

//Driver Code Starts
#include <iostream>
#include<climits>
using namespace std;

// Node structure
class Node {
  public:
    int data;
    Node *left;
    Node *right;

    Node(int val) {
        data = val;
        left = nullptr;
        right = nullptr;
    }
};
//Driver Code Ends


// Custom data type to keep track of Minimum,Maximum value,
// and Size of the largest BST
class BSTInfo {
  public:
    int mini;
    int maxi;
    int mxSz;

    BSTInfo(int mn, int mx, int sz) {
        mini = mn;
        maxi = mx;
        mxSz = sz;
    }
};

// Recursive Function to find maximum size
BSTInfo largestBSTBT(Node *root) {
    if (!root)
        return BSTInfo(INT_MAX, INT_MIN, 0);

    BSTInfo left = largestBSTBT(root->left);
    BSTInfo right = largestBSTBT(root->right);

    // Check if the current subtree is a BST
    if (left.maxi < root->data && right.mini > root->data) {
        return BSTInfo(min(left.mini, root->data), 
                       max(right.maxi, root->data), 1 + left.mxSz + right.mxSz);
    }

    return BSTInfo(INT_MIN, INT_MAX, max(left.mxSz, right.mxSz));
}

// Function to return the size of the largest BST
int largestBST(Node *root) {
    return largestBSTBT(root).mxSz;
}


//Driver Code Starts
int main() {
  
  // Constructed binary tree 
  //         5
  //       /   \
  //      2     4
  //     / \
  //    1   3

    Node *root = new Node(5);
    root->left = new Node(2);
    root->right = new Node(4);
    root->left->left = new Node(1);
    root->left->right = new Node(3);

    cout << largestBST(root) << endl;

    return 0;
}

//Driver Code Ends

Java

//Driver Code Starts
// Node structure
class Node {
    int data;
    Node left;
    Node right;

    Node(int val) {
        data = val;
        left = null;
        right = null;
    }
}
//Driver Code Ends


// Custom data type to keep track of Minimum, Maximum value,
// and Size of the largest BST
class BSTInfo {
    int mini;
    int maxi;
    int mxSz;

    BSTInfo(int mn, int mx, int sz) {
        mini = mn;
        maxi = mx;
        mxSz = sz;
    }
}

public class LargestBST {

    // Recursive Function to find maximum size
    static BSTInfo largestBSTBT(Node root) {
        if (root == null)
            return new BSTInfo(Integer.MAX_VALUE, Integer.MIN_VALUE, 0);

        BSTInfo left = largestBSTBT(root.left);
        BSTInfo right = largestBSTBT(root.right);

        // Check if the current subtree is a BST
        if (left.maxi < root.data && right.mini > root.data) {
            return new BSTInfo(Math.min(left.mini, root.data),
                               Math.max(right.maxi, root.data),
                               1 + left.mxSz + right.mxSz);
        }

        return new BSTInfo(Integer.MIN_VALUE, Integer.MAX_VALUE, Math.max(left.mxSz, right.mxSz));
    }

    // Function to return the size of the largest BST
    static int largestBst(Node root) {
        return largestBSTBT(root).mxSz;
    }


//Driver Code Starts
    public static void main(String[] args) {
        
        // Constructed binary tree 
        //         5
        //       /   \
        //      2     4
        //     / \
        //    1   3
        Node root = new Node(5);
        root.left = new Node(2);
        root.right = new Node(4);
        root.left.left = new Node(1);
        root.left.right = new Node(3);

        System.out.println(largestBst(root));
    }
}

//Driver Code Ends

Python

#Driver Code Starts
import sys


# Node structure
class Node:
    def __init__(self, val):
        self.data = val
        self.left = None
        self.right = None

#Driver Code Ends


# Custom data type to keep track of Minimum, Maximum value,
# and Size of the largest BST
class BSTInfo:
    def __init__(self, mn, mx, sz):
        self.mini = mn
        self.maxi = mx
        self.mxSz = sz


# Recursive Function to find maximum size
def largestBSTBT(root):
    if not root:
        return BSTInfo(sys.maxsize, -sys.maxsize, 0)

    left = largestBSTBT(root.left)
    right = largestBSTBT(root.right)

    # Check if the current subtree is a BST
    if left.maxi < root.data and right.mini > root.data:
        return BSTInfo(min(left.mini, root.data),
                       max(right.maxi, root.data),
                       1 + left.mxSz + right.mxSz)

    return BSTInfo(-sys.maxsize, sys.maxsize, max(left.mxSz, right.mxSz))


# Function to return the size of the largest BST
def largestBst(root):
    return largestBSTBT(root).mxSz


#Driver Code Starts

if __name__ == "__main__":
    
    # Constructed binary tree 
    #         5
    #       /   \
    #      2     4
    #     / \
    #    1   3
    root = Node(5)
    root.left = Node(2)
    root.right = Node(4)
    root.left.left = Node(1)
    root.left.right = Node(3)

    print(largestBst(root))
#Driver Code Ends

C#

//Driver Code Starts
using System;

// Node structure
class Node {
    public int data;
    public Node left, right;

    public Node(int val) {
        data = val;
        left = null;
        right = null;
    }
}
//Driver Code Ends


// Custom data type to keep track of Minimum, Maximum value,
// and Size of the largest BST
class BSTInfo {
    public int mini;
    public int maxi;
    public int mxSz;

    public BSTInfo(int mn, int mx, int sz) {
        mini = mn;
        maxi = mx;
        mxSz = sz;
    }
}

class LargestBST {

    // Recursive Function to find maximum size
    static BSTInfo largestBSTBT(Node root) {
        if (root == null)
            return new BSTInfo(int.MaxValue, int.MinValue, 0);

        BSTInfo left = largestBSTBT(root.left);
        BSTInfo right = largestBSTBT(root.right);

        // Check if the current subtree is a BST
        if (left.maxi < root.data && right.mini > root.data) {
            return new BSTInfo(Math.Min(left.mini, root.data),
                               Math.Max(right.maxi, root.data),
                               1 + left.mxSz + right.mxSz);
        }

        return new BSTInfo(int.MinValue, int.MaxValue, Math.Max(left.mxSz, right.mxSz));
    }

    // Function to return the size of the largest BST
    static int largestBst(Node root) {
        return largestBSTBT(root).mxSz;
    }


//Driver Code Starts
    static void Main(string[] args) {
        
        
        // Constructed binary tree 
        //         5
        //       /   \
        //      2     4
        //     / \
        //    1   3
        Node root = new Node(5);
        root.left = new Node(2);
        root.right = new Node(4);
        root.left.left = new Node(1);
        root.left.right = new Node(3);

        Console.WriteLine(largestBst(root));
    }
}

//Driver Code Ends

JavaScript

//Driver Code Starts
// Node structure
class Node {
    constructor(val) {
        this.data = val;
        this.left = null;
        this.right = null;
    }
}

//Driver Code Ends

// Custom data type to keep track of Minimum, Maximum value,
// and Size of the largest BST
class BSTInfo {
    constructor(mn, mx, sz) {
        this.mini = mn;
        this.maxi = mx;
        this.mxSz = sz;
    }
}

// Recursive Function to find maximum size
function largestBSTBT(root) {
    if (!root)
        return new BSTInfo(Number.MAX_SAFE_INTEGER, Number.MIN_SAFE_INTEGER, 0);

    let left = largestBSTBT(root.left);
    let right = largestBSTBT(root.right);

    // Check if the current subtree is a BST
    if (left.maxi < root.data && right.mini > root.data) {
        return new BSTInfo(Math.min(left.mini, root.data),
                           Math.max(right.maxi, root.data),
                           1 + left.mxSz + right.mxSz);
    }

    return new BSTInfo(Number.MIN_SAFE_INTEGER, Number.MAX_SAFE_INTEGER, Math.max(left.mxSz, right.mxSz));
}

// Function to return the size of the largest BST
function largestBst(root) {
    return largestBSTBT(root).mxSz;
}


//Driver Code Starts
// Driver Code
// Constructed binary tree 
//         5
//       /   \
//      2     4
//     / \
//    1   3
let root = new Node(5);
root.left = new Node(2);
root.right = new Node(4);
root.left.left = new Node(1);
root.left.right = new Node(3);

console.log(largestBst(root));
//Driver Code Ends

Output

Comment

Article Tags:

Binary Search Tree

Explore

DSA Fundamentals

Data Structures

Algorithms

Advanced

Interview Preparation

Practice Problem