-
Notifications
You must be signed in to change notification settings - Fork 57
/
Largest_BST.cpp
111 lines (104 loc) · 1.49 KB
/
Largest_BST.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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include<iostream>
#include<climits>
using namespace std;
class node
{
public:
int data;
node*left;
node*right;
node(int d)
{
data=d;
left=NULL;
right=NULL;
}
};
node* insertinbst(node* root,int data)
{
if(root==NULL)
{
return new node(data);
}
if (data<=root->data)
{
insertinbst(root->left,data);
}
else
{
insertinbst(root->right,data);
}
return root;
}
node* build()
{
node* root=NULL;
int d;
cin>>d;
while(d!=-1)
{
root=insertinbst(root,d);
cin>>d;
}
return root;
}/*
bool is_bst(node* root,int minv=INT_MIN,int maxv=INT_MAX)
{
if(root==NULL)
{
return true;
}
if(root->data>=minv and root->data<=maxv and is_bst(root->left,minv,root->data) and is_bst(root->right,root->data,maxv))
{
return true;
}
else
{
return false;
}
}*/
class info
{
public:
int size;
int max;
int min;
int ans;
bool is_bst;
};
info larg_BST(node* root)
{
if(root==NULL)
{
return {0,INT_MIN,INT_MAX,0,true};
}
if(root->left==NULL and root->right==NULL)
{
return {1,root->data,root->data,1,true};
}
info l=larg_BST(root->left);
info r=larg_BST(root->right);
info i;
i.size=(1+ l.size + r.size);
if(l.is_bst and r.is_bst and l.max<root->data and r.min>root->data)
{
i.min=min(l.min,min(r.min,root->data));
i.max=max(l.max,min(r.max,root->data));
i.ans=i.size;
i.is_bst=true;
return i;
}
i.ans=max(l.ans,r.ans);
i.is_bst=false;
return i;
}
int main()
{
node* root=build();
cout<<larg_BST(root).ans;
}
/*
5 3 7 1 6 8 -1
o/p:
??
*/