Largest BST Subtree solution and explanation
9 more videos on this problem
Largest BST Subtree - Solution | Binary Trees | Data Structure and Algorithms in JAVAPepcoding · 28:09 · 22K views
LARGEST BST SUBSTREE | LEETCODE # 333 | PYTHON POSTORDER DFS SOLUTIONCracking FAANG · 16:28 · 3K views
leetcode 333 largest bst subtreeCodebix · 8:52 · 3K views
Largest BST Subtree LeetCode Google Chrome 12 13 2018 5 17 38 PMScott · 3:24 · 1K views
Facebook Coding Interview Question | Leetcode 333 | Largest BST SubtreeWorkWithGoogler · 17:16 · 746 views
333. Largest BST Subtree - Week 1/5 Leetcode July ChallengeProgramming Live with Larry · 13:30 · 495 views
333. Largest BST Subtree (Leetcode Medium)Programming Live with Larry · 9:21 · 412 views
Largest BST in Binary Tree | Leetcode-333 and GeekforGeeks | UpSkill with YathaarthUpSkill with Yathaarth · 36:39 · 306 views
LeetCode 333 Largest BST Subtree | Java | O(n)How we live in Texas · 13:33 · 253 views
Leetcode 333 Largest BST Subtree 二叉搜索树+子树节点个数大叔与小白 · 9:34 · 138 views
The problem
Given the root of a binary tree, find the largest subtree, which is also a Binary Search Tree (BST), where the largest means subtree has the largest number of nodes.
A Binary Search Tree (BST) is a tree in which all the nodes follow the below-mentioned properties:
- The left subtree values are less than the value of their parent (root) node's value.
- The right subtree values are greater than the value of their parent (root) node's value.
Note: A subtree must include all of its descendants.
Example 1:
Input: root = [10,5,15,1,8,null,7] Output: 3 Explanation: The Largest BST Subtree in this case is the highlighted one. The return value is the subtree's size, which is 3.
Example 2:
Input: root = [4,2,7,2,3,5,null,2,null,null,null,null,null,1] Output: 2
Constraints:
- The number of nodes in the tree is in the range
[0, 104]. -104 <= Node.val <= 104
Follow up: Can you figure out ways to solve it with O(n) time complexity?
Approach overview
Problem Overview: You are given a binary tree that is not necessarily a binary search tree. The task is to find the size (number of nodes) of the largest subtree that satisfies the Binary Search Tree property. A subtree counts only if every node inside it follows the BST rule: left values are smaller and right values are larger.
Approach 1: Validate Every Subtree (Brute Force) (Time: O(n^2), Space: O(h))
The direct idea is to treat every node as the root of a potential BST. For each node, run a validation check to confirm whether the subtree rooted at that node satisfies BST rules. The validation function recursively ensures left < root < right while computing the subtree size. If the subtree is valid, update the global maximum size. Because each validation may traverse many nodes repeatedly, the worst-case complexity becomes O(n^2) when the tree is skewed. Space complexity is O(h) due to recursion depth. This approach is straightforward but inefficient for large trees.
Approach 2: Postorder DFS with Subtree Metadata (Optimal) (Time: O(n), Space: O(h))
The optimal solution uses a single postorder traversal from the leaves upward. Each DFS call returns metadata about the current subtree: whether it forms a BST, its size, and the minimum and maximum values inside it. While returning from recursion, you combine the results from the left and right children. A subtree is a valid BST if the left and right subtrees are BSTs and left.max < node.val < right.min. When this condition holds, the subtree size becomes left.size + right.size + 1, and the min/max boundaries are updated accordingly.
If the condition fails, the subtree is marked invalid so its parent cannot treat it as part of a BST. During traversal you maintain a global maximum representing the largest valid BST encountered so far. Each node is processed exactly once, giving O(n) time complexity and O(h) space for recursion. This technique is a classic combination of Depth-First Search and bottom-up state aggregation similar to Dynamic Programming on trees.
The key insight is that every subtree can summarize enough information (min, max, size, validity) for its parent to make a constant-time decision. This avoids repeatedly scanning subtrees. The pattern appears frequently in binary tree problems where parent decisions depend on child properties.
Recommended for interviews: The postorder DFS solution is what interviewers expect. Mentioning the brute force approach first demonstrates understanding of the problem structure. Transitioning to the single-pass postorder solution shows optimization skills and familiarity with bottom-up tree processing.
Solution
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def largestBSTSubtree(self, root: Optional[TreeNode]) -> int:
def dfs(root):
if root is None:
return inf, -inf, 0
lmi, lmx, ln = dfs(root.left)
rmi, rmx, rn = dfs(root.right)
nonlocal ans
if lmx < root.val < rmi:
ans = max(ans, ln + rn + 1)
return min(lmi, root.val), max(rmx, root.val), ln + rn + 1
return -inf, inf, 0
ans = 0
dfs(root)
return ans/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private int ans;
public int largestBSTSubtree(TreeNode root) {
ans = 0;
dfs(root);
return ans;
}
private int[] dfs(TreeNode root) {
if (root == null) {
return new int[] {Integer.MAX_VALUE, Integer.MIN_VALUE, 0};
}
int[] left = dfs(root.left);
int[] right = dfs(root.right);
if (left[1] < root.val && root.val < right[0]) {
ans = Math.max(ans, left[2] + right[2] + 1);
return new int[] {
Math.min(root.val, left[0]), Math.max(root.val, right[1]), left[2] + right[2] + 1};
}
return new int[] {Integer.MIN_VALUE, Integer.MAX_VALUE, 0};
}
}/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int ans;
int largestBSTSubtree(TreeNode* root) {
ans = 0;
dfs(root);
return ans;
}
vector<int> dfs(TreeNode* root) {
if (!root) return {INT_MAX, INT_MIN, 0};
auto left = dfs(root->left);
auto right = dfs(root->right);
if (left[1] < root->val && root->val < right[0]) {
ans = max(ans, left[2] + right[2] + 1);
return {min(root->val, left[0]), max(root->val, right[1]), left[2] + right[2] + 1};
}
return {INT_MIN, INT_MAX, 0};
}
};/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func largestBSTSubtree(root *TreeNode) int {
ans := 0
var dfs func(root *TreeNode) []int
dfs = func(root *TreeNode) []int {
if root == nil {
return []int{math.MaxInt32, math.MinInt32, 0}
}
left := dfs(root.Left)
right := dfs(root.Right)
if left[1] < root.Val && root.Val < right[0] {
ans = max(ans, left[2]+right[2]+1)
return []int{min(root.Val, left[0]), max(root.Val, right[1]), left[2] + right[2] + 1}
}
return []int{math.MinInt32, math.MaxInt32, 0}
}
dfs(root)
return ans
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Validate Each Subtree (Brute Force) | O(n^2) | O(h) | Good for understanding the problem and small trees where repeated validation cost is acceptable |
| Postorder DFS with Min/Max Tracking | O(n) | O(h) | Best general solution. Processes each node once and scales well for large trees |
Frequently asked questions
Is Largest BST Subtree easy or hard?
Largest BST Subtree is generally rated Medium on coding platforms. The difficulty comes from combining BST validation with subtree aggregation in a single traversal. Once the idea of returning metadata from each DFS call is understood, the implementation becomes straightforward.
Largest BST Subtree Python/Java solution
Most implementations use a recursive DFS function that returns a tuple or object containing isBST, size, min, and max values. Python typically returns a tuple, while Java and C++ often use a custom class or struct. The logic remains the same across languages and runs in O(n) time.
How to solve Largest BST Subtree in O(n)?
Use a postorder depth-first traversal that returns four values for each subtree: whether it is a BST, the subtree size, the minimum value, and the maximum value. If both children are BSTs and their values satisfy left.max < node.val < right.min, the current subtree forms a BST. Update the size and propagate boundaries upward while tracking the largest size globally.
What is the best approach for Largest BST Subtree?
The best approach is a postorder DFS that returns subtree metadata: whether the subtree is a BST, its size, and its min and max values. Each node combines results from its left and right children to determine if it forms a valid BST. This processes every node once, giving O(n) time complexity and O(h) recursion space.
Is Largest BST Subtree asked at Google/Amazon/Meta?
Largest BST Subtree and similar tree-validation problems frequently appear in interviews at companies like Google, Amazon, and Meta. They test understanding of binary search tree properties, recursive traversal, and bottom-up reasoning on trees.
What data structure is used in Largest BST Subtree?
The problem uses a binary tree as the primary data structure. The optimal algorithm relies on depth-first search recursion and tracks metadata such as subtree minimum, maximum, and size to verify Binary Search Tree properties.
What is the time complexity of Largest BST Subtree?
The optimal solution runs in O(n) time because each node in the binary tree is visited exactly once during a postorder traversal. The brute force method that validates every subtree can take O(n^2) time in the worst case. Space complexity for the optimal approach is O(h), where h is the height of the tree.