# Leetcode 333 Solution

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

## Solution

``````/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
int res = 0;

public:
bool largestBSTSubtree(TreeNode* root, int& min_val, int& max_val, int& size)
{
if (root == NULL)
{
size = 0;
max_val = INT_MIN;
min_val = INT_MAX;
return true;
}

int left_size, left_min, left_max;
bool left_bst = largestBSTSubtree(root->left, left_min, left_max, left_size);

int right_size, right_min, right_max;
bool right_bst = largestBSTSubtree(root->right, right_min, right_max, right_size);

size = 1 + left_size + right_size;

bool valid = (left_max < root->val && root->val < right_min) && left_bst && right_bst;

if (valid)
res = max(size, res);

min_val = root->val;
min_val = min(min_val, left_min);
min_val = min(min_val, right_min);

max_val = root->val;
max_val = max(root->val, left_max);
max_val = max(root->val, right_max);

return valid;
}

int largestBSTSubtree(TreeNode* root) {
int size = 0;
int min_val, max_val;
largestBSTSubtree(root, min_val, max_val, size);
return res;
}
};
``````