# 333. Largest BST Subtree

Given a binary tree, find the largest subtree which is a Binary Search Tree (BST), where largest means subtree with largest number of nodes in it.

Note:
A subtree must include all of its descendants.

Example:

``````Input: [10,5,15,1,8,null,7]

10
/ \
5  15
/ \   \
1   8   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.
``````

Can you figure out ways to solve it with O(n) time complexity?

Hint:

1. You can recursively use algorithm similar to 98. Validate Binary Search Tree at each node of the tree, which will result in O(nlogn) time complexity.

``````class Solution {
public:
int largestBSTSubtree(TreeNode* root) {
int res = 0;
dfs(root, res);
return res;
}
void dfs(TreeNode *root, int &res) {
if (!root) return;
int d = countBFS(root, INT_MIN, INT_MAX);
if (d != -1) {
res = max(res, d);
return;
}
dfs(root->left, res);
dfs(root->right, res);
}
int countBFS(TreeNode *root, int mn, int mx) {
if (!root) return 0;
if (root->val <= mn || root->val >= mx) return -1;
int left = countBFS(root->left, mn, root->val);
if (left == -1) return -1;
int right = countBFS(root->right, root->val, mx);
if (right == -1) return -1;
return left + right + 1;
}
};
``````

``````class Solution {
public:
int largestBSTSubtree(TreeNode* root) {
if (!root) return 0;
if (isValid(root, INT_MIN, INT_MAX)) return count(root);
return max(largestBSTSubtree(root->left), largestBSTSubtree(root->right));
}
bool isValid(TreeNode* root, int mn, int mx) {
if (!root) return true;
if (root->val <= mn || root->val >= mx) return false;
return isValid(root->left, mn, root->val) && isValid(root->right, root->val, mx);
}
int count(TreeNode* root) {
if (!root) return 0;
return count(root->left) + count(root->right) + 1;
}
};
``````

``````class Solution {
public:
int largestBSTSubtree(TreeNode* root) {
int res = 0, mn = INT_MIN, mx = INT_MAX;
isValidBST(root, mn, mx, res);
return res;
}
void isValidBST(TreeNode* root, int& mn, int& mx, int& res) {
if (!root) return;
int left_cnt = 0, right_cnt = 0, left_mn = INT_MIN;
int right_mn = INT_MIN, left_mx = INT_MAX, right_mx = INT_MAX;
isValidBST(root->left, left_mn, left_mx, left_cnt);
isValidBST(root->right, right_mn, right_mx, right_cnt);
if ((!root->left || root->val > left_mx) && (!root->right || root->val < right_mn)) {
res = left_cnt + right_cnt + 1;
mn = root->left ? left_mn : root->val;
mx = root->right ? right_mx : root->val;
} else {
res = max(left_cnt, right_cnt);
}
}
};
``````

``````class Solution {
public:
int largestBSTSubtree(TreeNode* root) {
vector<int> res = helper(root);
return res[2];
}
vector<int> helper(TreeNode* node) {
if (!node) return {INT_MAX, INT_MIN, 0};
vector<int> left = helper(node->left), right = helper(node->right);
if (node->val > left[1] && node->val < right[0]) {
return {min(node->val, left[0]), max(node->val, right[1]), left[2] + right[2] + 1};
} else {
return {INT_MIN, INT_MAX, max(left[2], right[2])};
}
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/333

Validate Binary Search Tree

https://leetcode.com/problems/largest-bst-subtree/

https://leetcode.com/problems/largest-bst-subtree/discuss/78892/12ms-C%2B%2B-solution

https://leetcode.com/problems/largest-bst-subtree/discuss/78899/Very-Short-Simple-Java-O(N)-Solution

https://leetcode.com/problems/largest-bst-subtree/discuss/78896/Clean-and-easy-to-understand-Java-Solution

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation