Largest BST in Binary Tree
A medium BST problem included in Love Babbar 450, Striver A2Z. Below: the roles whose interviews prioritise this topic, and how to practise it.
- Topic
- BST
- Sheets
- 2
- Core for
- 2 roles
- Platform
- GeeksforGeeks
The problem
Given the root of a binary tree, find the size of the largest subtree that is also a valid binary search tree. A subtree is a tree consisting of a node and all its descendants.
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-09Checking 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
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.
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.
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.
What each operation costs
| Operation | Time |
|---|---|
| search, insert, or delete on balanced tree | O(log n) |
| search, insert, or delete on degenerate line tree | O(n) |
| in-order traversal visiting all nodes in sorted order | O(n) |
What usually goes wrong with BST
- Validating a tree by checking only immediate children against the parent, missing violations where a node deep in the left subtree is larger than an ancestor higher up.
- Allowing duplicate values on the wrong side when the problem specification requires strictly smaller values on the left and strictly greater on the right.
- Deleting a node with two children by removing it directly instead of replacing its value with its in-order predecessor or successor and deleting that leaf instead.
Which roles need this problem
BST is a core topic for these 2 roles — if you're targeting one of them, this problem is early in your path, not optional.
Secondary for 6 more roles, including Full-Stack Developer, Android Developer, iOS Developer.
Companies that have asked it
Tags taken from the problem's own GeeksforGeeks page — not a copied list.
Track this in your role's order
Pick your target role and all 370 problems — including this one — resequence to what that interview actually asks. Free.
Start freeMore BST problems
Problem set and role mapping as of .