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, Python, C++ and JavaScript, 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.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
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 code in Java, Python, C++ and JavaScript.
| 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);
}
}class Solution:
def largestBst(self, root: Optional[TreeNode]) -> int:
if root is None:
return 0
if self.valid(root, float('-inf'), float('inf')):
return self.size(root)
return max(self.largestBst(root.left), self.largestBst(root.right))
def valid(self, n: Optional[TreeNode], lo: float, hi: float) -> bool:
if n is None:
return True
if n.val <= lo or n.val >= hi:
return False
return self.valid(n.left, lo, n.val) and self.valid(n.right, n.val, hi)
def size(self, n: Optional[TreeNode]) -> int:
return 0 if n is None else 1 + self.size(n.left) + self.size(n.right)class Solution {
public:
static int largestBst(TreeNode* root) {
if (root == nullptr) return 0;
if (valid(root, LLONG_MIN, LLONG_MAX)) return size(root);
return max(largestBst(root->left), largestBst(root->right));
}
private:
static bool valid(TreeNode* n, long long lo, long long hi) {
if (n == nullptr) return true;
if (n->val <= lo || n->val >= hi) return false;
return valid(n->left, lo, n->val) && valid(n->right, n->val, hi);
}
static int size(TreeNode* n) {
return n == nullptr ? 0 : 1 + size(n->left) + size(n->right);
}
};function largestBst(root) {
if (root === null) return 0;
if (valid(root, -Infinity, Infinity)) return size(root);
return Math.max(largestBst(root.left), largestBst(root.right));
}
function valid(n, lo, 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);
}
function size(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]) };
}
}INT_MAX = 2**31 - 1
INT_MIN = -2**31
class Solution:
def largestBst(self, root: Optional[TreeNode]) -> int:
return self.post(root)[2]
# returns (min, max, size); for non-BST subtrees size is the best size found below
def post(self, n: Optional[TreeNode]) -> Tuple[int, int, int]:
if n is None:
return (INT_MAX, INT_MIN, 0)
l, r = self.post(n.left), self.post(n.right)
if l[1] < n.val < r[0]:
return (min(n.val, l[0]), max(n.val, r[1]), l[2] + r[2] + 1)
return (INT_MIN, INT_MAX, max(l[2], r[2]))class Solution {
public:
static int largestBst(TreeNode* root) {
return post(root)[2];
}
private:
// returns {min, max, size}; for non-BST subtrees size is the best size found below
static array<int, 3> post(TreeNode* n) {
if (n == nullptr) return { INT_MAX, INT_MIN, 0 };
array<int, 3> l = post(n->left), r = post(n->right);
if (l[1] < n->val && n->val < r[0]) {
return { min(n->val, l[0]), max(n->val, r[1]), l[2] + r[2] + 1 };
}
return { INT_MIN, INT_MAX, max(l[2], r[2]) };
}
};const INT_MAX = 2147483647;
const INT_MIN = -2147483648;
function largestBst(root) {
return post(root)[2];
}
// returns [min, max, size]; for non-BST subtrees size is the best size found below
function post(n) {
if (n === null) return [INT_MAX, INT_MIN, 0];
const l = post(n.left), r = post(n.right);
if (l[1] < n.val && n.val < r[0]) {
return [Math.min(n.val, l[0]), Math.max(n.val, r[1]), l[2] + r[2] + 1];
}
return [INT_MIN, INT_MAX, 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).