# Share my C++ solution with only one dfs-pass

• ``````/**
* 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 {
public:
int largestBSTSubtree(TreeNode* root) {
map<TreeNode*, int> sz;
map<TreeNode*, pair<int, int> > min_max;
int ans = 0;
check(root, sz, min_max, ans);
return ans;
}
#define mi first
#define ma second
#define MP make_pair
bool check(TreeNode *root, map<TreeNode*, int> &sz, map<TreeNode*, pair<int, int> > &min_max, int &ans) {
if (root == NULL) return true;
bool left_good = check(root->left, sz, min_max, ans),
right_good = check(root->right, sz, min_max, ans);
if (!left_good or !right_good) return false;
if (root->left != NULL and min_max[root->left].ma > root->val) return false;
if (root->right != NULL and min_max[root->right].mi < root->val) return false;
min_max[root] = MP(root->val, root->val);
if (root->left != NULL) min_max[root].mi = min_max[root->left].mi;
if (root->right != NULL) min_max[root].ma = min_max[root->right].ma;
sz[root] = 1;
if (root->left != NULL) sz[root] += sz[root->left];
if (root->right != NULL) sz[root] += sz[root->right];
ans = max(ans, sz[root]);
return true;
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.