Largest BST
Largest BST is a medium trees & bst problem solved with the postorder + multiple return values pattern.
The best approach, optimal (postorder with multiple return values), runs in O(n) time and O(h) space.
Below are 2 approaches in Java, from validate every subtree up.
Problem
Return the number of nodes in the largest subtree that is a valid BST. A subtree means a node together with all of its descendants.
Examples
Example 1
- Input
root = [5, 2, 4, 1, 3]- Output
3- Why
- The subtree [2, 1, 3] is a BST; the whole tree is not, since 4 > 5 is false.
Example 2
- Input
root = [6, 7, 3, null, 2, 2, 4]- Output
3- Why
- [3, 2, 4] is the largest BST.
Constraints
- The tree has
1to10^5nodes. - Count nodes in the largest subtree that is a valid BST.
Animated walkthrough
A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.
Concepts first, then the problem and every approach, step by step.
Space to play or pause · ← → to jump a step · click or drag the bar to seek
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.
| Approach | Time | Space |
|---|---|---|
| Validate every subtree | O(n²) | O(h) |
| Optimal (postorder with multiple return values) | O(n) | O(h) |
1Validate every subtree
O(n²)O(h)For each node, check whether its subtree is a BST with the range method and count its size. Keep the best.
- largest(n) = isBST(n) ? size(n) : max(largest(left), largest(right)).
class Solution {
static int largestBst(TreeNode root) {
if (root == null) return 0;
if (valid(root, Long.MIN_VALUE, Long.MAX_VALUE)) return size(root);
return Math.max(largestBst(root.left), largestBst(root.right));
}
private static boolean valid(TreeNode n, long lo, long hi) {
if (n == null) return true;
if (n.val <= lo || n.val >= hi) return false;
return valid(n.left, lo, n.val) && valid(n.right, n.val, hi);
}
private static int size(TreeNode n) {
return n == null ? 0 : 1 + size(n.left) + size(n.right);
}
}2Optimal (postorder with multiple return values)
O(n)O(h)Return {min, max, size} from each subtree. A node forms a BST when left.max < val < right.min. Then its min, max and size combine the children's. If it is not a BST, report an impossible range (min = -inf, max = +inf) so no ancestor can be a BST, and carry the best size found below.
- null → {MAX, MIN, 0} so any parent accepts it.
- If left.max < val < right.min: {min(val, left.min), max(val, right.max), left.size + right.size + 1}.
- Else: {MIN, MAX, max(left.size, right.size)}.
class Solution {
static int largestBst(TreeNode root) {
return post(root)[2];
}
// returns {min, max, size}; for non-BST subtrees size is the best size found below
private static int[] post(TreeNode n) {
if (n == null) return new int[] { Integer.MAX_VALUE, Integer.MIN_VALUE, 0 };
int[] l = post(n.left), r = post(n.right);
if (l[1] < n.val && n.val < r[0]) {
return new int[] { Math.min(n.val, l[0]), Math.max(n.val, r[1]), l[2] + r[2] + 1 };
}
return new int[] { Integer.MIN_VALUE, Integer.MAX_VALUE, Math.max(l[2], r[2]) };
}
}Edge cases to test
- Whole tree is a BST
- Only leaves are BSTs (answer 1)
Hints
Hint 1
Each subtree reports four things upward: is it a BST, its size, its min and its max.
FAQ
What is the best time complexity for Largest BST?
Optimal (postorder with multiple return values) runs in O(n) time and O(h) extra space.
Which pattern does Largest BST use?
It is a trees & bst problem that uses the postorder + multiple return values pattern. Other problems with the same pattern: Balanced Binary Tree, Validate Binary Search Tree, Children Sum in a Binary Tree.
Is there a brute force solution for Largest BST?
Yes. Validate every subtree takes O(n²) time and O(h) space. For each node, check whether its subtree is a BST with the range method and count its size.
Which edge cases should I test for Largest BST?
Whole tree is a BST; Only leaves are BSTs (answer 1).