Binary Search TreesProblem 21 of 22Important
Largest BST in a Binary Tree [V.V.V.V.V IMP]
Problem Statement
Given a Binary Tree, find the size (number of nodes) of the largest subtree which is also a valid Binary Search Tree. If the entire tree is a BST, return the size of the whole tree.
Example:
10
/ \
5 15
/ \ \
1 8 7
The largest BST subtree is:
5
/ \
1 8
Size = 3
Note: The right subtree (15, 7) is not a BST because 7 < 15 but is on the right.
Approach 1: Brute Force (Check Each Subtree)
Intuition
For every node, check if the subtree rooted at that node is a valid BST. If yes, count its nodes. Track the maximum.
Algorithm
- For each node, check if subtree is a valid BST
- If valid, count nodes in subtree
- If not valid, recursively check left and right subtrees
- Return maximum size found
java
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
private boolean isBST(TreeNode root, long minVal, long maxVal) {
if (root == null) return true;
if (root.val <= minVal || root.val >= maxVal) {
return false;
}
return isBST(root.left, minVal, root.val) &&
isBST(root.right, root.val, maxVal);
}
private int countNodes(TreeNode root) {
if (root == null) return 0;
return 1 + countNodes(root.left) + countNodes(root.right);
}
public int largestBSTBruteForce(TreeNode root) {
if (root == null) return 0;
if (isBST(root, Long.MIN_VALUE, Long.MAX_VALUE)) {
return countNodes(root);
}
return Math.max(largestBSTBruteForce(root.left),
largestBSTBruteForce(root.right));
}
}Complexity Analysis
- Time Complexity: O(n^3) worst case - For each node O(n), check BST O(n), count O(n)
- Space Complexity: O(n) - Recursion stack
Approach 2: Optimal (Post-order with Info Propagation)
Intuition
Process bottom-up. Each subtree returns:
- Whether it's a valid BST
- Its size
- Min and max values in the subtree
A subtree is BST if:
- Left subtree is BST
- Right subtree is BST
- Left max < root < Right min
Algorithm
- Use post-order traversal
- Return tuple: (isBST, size, min, max)
- Combine results from children to determine if current subtree is BST
- Track maximum BST size found
java
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
class NodeInfo {
boolean isBST;
int size;
int minVal;
int maxVal;
NodeInfo(boolean b, int s, int mn, int mx) {
isBST = b;
size = s;
minVal = mn;
maxVal = mx;
}
}
public class Solution {
private int maxSize = 0;
private NodeInfo solve(TreeNode root) {
if (root == null) {
return new NodeInfo(true, 0, Integer.MAX_VALUE, Integer.MIN_VALUE);
}
NodeInfo left = solve(root.left);
NodeInfo right = solve(root.right);
// Check if current subtree is BST
if (left.isBST && right.isBST &&
left.maxVal < root.val && root.val < right.minVal) {
int size = 1 + left.size + right.size;
maxSize = Math.max(maxSize, size);
return new NodeInfo(
true,
size,
Math.min(root.val, left.minVal),
Math.max(root.val, right.maxVal)
);
}
// Not a BST
return new NodeInfo(false, 0, 0, 0);
}
public int largestBST(TreeNode root) {
maxSize = 0;
solve(root);
return maxSize;
}
}Complexity Analysis
- Time Complexity: O(n) - Each node visited once
- Space Complexity: O(h) - Recursion stack
Approach 3: Return Size Directly
Intuition
Instead of tracking max in a global variable, we can return -1 for non-BST subtrees and propagate the maximum size found.
Algorithm
- Return
{size, min, max}if valid BST - Return negative size to indicate not BST but carry the max BST size found below
java
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
// Returns [size, min, max]
// Negative size means not BST, abs is largest BST below
private int[] largestBSTHelper(TreeNode root) {
if (root == null) {
return new int[]{0, Integer.MAX_VALUE, Integer.MIN_VALUE};
}
int[] left = largestBSTHelper(root.left);
int[] right = largestBSTHelper(root.right);
// Both children are BSTs and satisfy BST property
if (left[0] >= 0 && right[0] >= 0 &&
left[2] < root.val && root.val < right[1]) {
int size = 1 + left[0] + right[0];
int minVal = (root.left == null) ? root.val : left[1];
int maxVal = (root.right == null) ? root.val : right[2];
return new int[]{size, minVal, maxVal};
}
// Not a BST
int maxFound = Math.max(Math.abs(left[0]), Math.abs(right[0]));
return new int[]{-maxFound, 0, 0};
}
public int largestBSTSize(TreeNode root) {
int[] result = largestBSTHelper(root);
return Math.abs(result[0]);
}
}Complexity Analysis
- Time Complexity: O(n)
- Space Complexity: O(h)
Approach 4: Cleaner Structure
Intuition
Use a clean structure that explicitly tracks all needed information.
java
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
class BSTInfo {
int size;
int minVal;
int maxVal;
boolean isBST;
BSTInfo(int s, int mn, int mx, boolean b) {
size = s; minVal = mn; maxVal = mx; isBST = b;
}
}
public class Solution {
private BSTInfo largestBSTUtil(TreeNode root) {
if (root == null) {
return new BSTInfo(0, Integer.MAX_VALUE, Integer.MIN_VALUE, true);
}
BSTInfo left = largestBSTUtil(root.left);
BSTInfo right = largestBSTUtil(root.right);
if (left.isBST && right.isBST &&
left.maxVal < root.val && root.val < right.minVal) {
return new BSTInfo(
1 + left.size + right.size,
Math.min(root.val, left.minVal),
Math.max(root.val, right.maxVal),
true
);
} else {
return new BSTInfo(
Math.max(left.size, right.size),
0, 0,
false
);
}
}
public int largestBSTSubtree(TreeNode root) {
return largestBSTUtil(root).size;
}
}Complexity Analysis
- Time Complexity: O(n)
- Space Complexity: O(h)
Key Takeaways
- Bottom-up approach: Key insight - process children first, then decide about current
- Information propagation: Pass min, max, size, and validity upward
- BST condition: left.max < root < right.min
- Very important problem: Frequently asked in interviews (VVVVV IMP)
- This is LeetCode #333 - Largest BST Subtree
- O(n) solution is elegant using post-order traversal
- The brute force O(n^3) is too slow and should be avoided