-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathLargest BST 22-07-24 POTD.cpp
37 lines (36 loc) · 1.04 KB
/
Largest BST 22-07-24 POTD.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// https://www.geeksforgeeks.org/problems/largest-bst/1
vector<int> fun(Node* root,int &mx){
if(root->left==NULL&&root->right==NULL)return {root->data,root->data,1};
if(root->right==NULL){
auto ls=fun(root->left,mx);
if(ls[2]&&ls[1]<root->data){
mx=max(mx,ls[2]+1);
return {min(ls[0],root->data),max(ls[1],root->data),ls[2]+1};
}
}
else if(root->left==NULL){
auto ls=fun(root->right,mx);
if(ls[2]&&ls[0]>root->data){
mx=max(mx,ls[2]+1);
return {min(ls[0],root->data),max(ls[1],root->data),ls[2]+1};
}
}
else{
auto ls=fun(root->left,mx);
auto rs=fun(root->right,mx);
if(ls[2]&&rs[2]&&ls[1]<root->data&&root->data<rs[0]){
mx=max(mx,ls[2]+rs[2]+1);
return {min(ls[0],root->data),max(rs[1],root->data),ls[2]+rs[2]+1};
}
}
return {0,0,0};
}
class Solution{
public:
int largestBst(Node *root)
{
int mx=1;
auto k=fun(root,mx);
return mx;
}
};