Largest BST Subtree - Practice Coding Problems

Largest BST Subtree - Problem

Given the root of a binary tree, find the largest subtree that is also a Binary Search Tree (BST).

The largest means the subtree with the maximum number of nodes.

A Binary Search Tree (BST) is a tree where:

The left subtree values are less than the parent node's value
The right subtree values are greater than the parent node's value

Note: A subtree must include all of its descendants.

Input & Output

Example 1 — Mixed Valid/Invalid BST

$ Input: root = [10,5,15,1,8,null,7]

› Output: 3

💡 Note: The left subtree [5,1,8] is a valid BST with 3 nodes. The right subtree [15,7] is invalid because 7 < 15. The whole tree is also invalid BST, so the largest BST subtree has 3 nodes.

Example 2 — Entire Tree is BST

$ Input: root = [4,2,6,1,3,5,7]

› Output: 7

💡 Note: The entire tree is a valid BST: left subtree values (1,2,3) < root (4) < right subtree values (5,6,7). All 7 nodes form the largest BST subtree.

Example 3 — Single Node

$ Input: root = [1]

› Output: 1

💡 Note: A single node is always a valid BST, so the largest BST subtree has 1 node.

Constraints

The number of nodes in the tree is in the range [0, 10⁴]
-10⁴ ≤ Node.val ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Binary tree with mixed valid/invalid BST subtrees

Validate Subtrees

Check BST property for each subtree using post-order traversal

Find Maximum

Return size of largest valid BST subtree found

Key Takeaway

🎯 Key Insight: Use post-order traversal to validate BST properties bottom-up while tracking subtree sizes efficiently

Asked in

G Google 25 a Amazon 20 M Microsoft 15 F Facebook 12

The key insight is to use post-order DFS to validate BST properties bottom-up while tracking subtree sizes. The optimal approach collects BST information (validity, size, min/max values) in a single traversal. Time: O(n), Space: O(h)

Common Approaches

Approach	Time	Space	Notes
✓ Optimized DFS - Single Pass	O(n)	O(h)	Post-order traversal collecting BST info and size in one pass
Brute Force - Validate Each Subtree	O(n²)	O(h)	Check if each subtree is a valid BST, then count its nodes

Optimized DFS - Single Pass — Algorithm Steps

Post-order traverse: visit children first
For each node, get BST info from children
Check if current subtree can form valid BST
Update global maximum size if valid BST found

Visualization

Tap to expand

Step-by-Step Walkthrough

Post-order DFS

Visit children first, collect BST info (valid, size, min, max)

Check BST Property

Use child info to validate current subtree BST property

Update Maximum

Track largest valid BST subtree size found so far

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <stdbool.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct BST {
    bool isBST;
    int size;
    int minVal;
    int maxVal;
};

struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int maxSize = 0;

struct BST dfs(struct TreeNode* node) {
    struct BST result;
    
    if (!node) {
        result.isBST = true;
        result.size = 0;
        result.minVal = INT_MAX;
        result.maxVal = INT_MIN;
        return result;
    }
    
    struct BST left = dfs(node->left);
    struct BST right = dfs(node->right);
    
    if (left.isBST && right.isBST && left.maxVal < node->val && node->val < right.minVal) {
        int size = left.size + right.size + 1;
        if (size > maxSize) maxSize = size;
        
        result.isBST = true;
        result.size = size;
        result.minVal = node->left ? left.minVal : node->val;
        result.maxVal = node->right ? right.maxVal : node->val;
    } else {
        result.isBST = false;
        result.size = 0;
        result.minVal = 0;
        result.maxVal = 0;
    }
    
    return result;
}

int solution(struct TreeNode* root) {
    maxSize = 0;
    dfs(root);
    return maxSize;
}

int main() {
    // For simplicity, create a test tree: [10,5,15,1,8,null,7]
    struct TreeNode* root = createNode(10);
    root->left = createNode(5);
    root->right = createNode(15);
    root->left->left = createNode(1);
    root->left->right = createNode(8);
    root->right->right = createNode(7);
    
    printf("%d\n", solution(root));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single traversal of all n nodes, each node visited exactly once

✓ Linear Growth

Space Complexity

O(h)

Recursion stack depth equals tree height h, plus BST info storage

✓ Linear Space

127.6K Views

Medium Frequency

~25 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized DFS - Single Pass — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler