# C++_O(n)_Bottom To Top method_with brief explanation

• Here we use bottom-to-top to traverse the Binary Tree. Now suppose you have a tree, now you are at the leaf node. So for each node, you will definitely construct a BST, for these leaves nodes parents, they should follow these rules:

1. root->val > max_value of left node,
2. root->val < min_value of right node.
So we can use these constraints to judge whether their parents can construct BSTs, if so, we can "merge" them into a larger node, which contains information of (number of nodes in these larger node, min_value, max_value).

Also we should set a variable to count our current max_number of our largest BST. Each time we successfully construct a BST, we update the value of this variable.

Repeat these step to our root value.

``````class Solution {
public:
int largestBSTSubtree(TreeNode* root) {
if(root == nullptr) return 0;
long res = 0;
dfs(root, res);
return res;
}
vector<long> dfs(TreeNode* root, long& res){
//NULL point means that we are now reaching beyond our leaf node, in order to make our leaf as a BST, we should set Max = LONG_MIN, Min = LONG_MAX;
if(root == nullptr) return {0, LONG_MAX, LONG_MIN};
auto L = dfs(root->left, res);
auto R = dfs(root->right, res);
if(root->val > L[2] && root->val < R[1]){
res = max(res, 1 + L[0] + R[0]);//update our result.

//merge into a larger node
L[1] = min(L[1], (long)root->val);
R[2] = max(R[2], (long)root->val);
return {1 + L[0] + R[0], L[1], R[2]};
}
return {0, LONG_MIN, LONG_MAX};
}
};``````

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