AlgoViz
HomeBinary Search Trees

Largest BST in Binary Tree

Hard

Return (min, max, size, isBST) from each subtree

Problem

Given a binary tree, return the size of the largest subtree that is itself a valid BST.

In simple words

Bottom-up, each node reports whether its subtree is a BST and how big; keep the largest one.

The idea

Compute bottom-up: a node roots a BST only if both children are BSTs and its value sits strictly between the left subtree's maximum and the right subtree's minimum. Returning those four facts from each call makes each node O(1) work and the whole tree O(n).

The trick

  • Bottom-up, single pass — checking each subtree independently would be O(n²).
  • Carry min, max, size and the validity flag together.
  • Leaves are BSTs of size 1 with sentinel bounds.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

10
5
15
1
8
7
0
1
2
3
4
5

Step 1 of 2. Here's the example — [10,5,15,1,8,null,7] Values: 10, 5, 15, 1, 8, 7.

1/2
Optimal
timeO(n)spaceO(h)
1post-order return (min,max,size,isBST)2if left.max<node<right.min and both BST: size=left+right+13else mark not BST; track best size

Input

array
[10, 5, 15, 1, 8, 7]

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
tree = [10,5,15,1,8,null,7]
Output:
3
Explanation:
The largest valid BST subtree has 3 nodes.

Example 2

Input:
tree = [5,2,4,1,3]
Output:
3
Explanation:
A 3-node subtree is the biggest BST.

Example 3

Input:
tree = [1]
Output:
1
Explanation:
A single node is a BST of size 1.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.