-
Notifications
You must be signed in to change notification settings - Fork 0
/
LargestBST.cpp
59 lines (49 loc) · 1.25 KB
/
LargestBST.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
/* Tree node structure used in the program
struct Node {
int data;
Node *left;
Node *right;
Node(int val) {
data = val;
left = right = NULL;
}
};*/
class info{
public:
int maxi;
int mini;
bool isBST;
int size;
};
class Solution{
public:
/*You are required to complete this method */
// Return the size of the largest sub-tree which is also a BST
info solve(Node*root,int &maxSize)
{
if(!root){
return {INT_MIN,INT_MAX,true,0};
}
info left=solve(root->left,maxSize);
info right=solve(root->right,maxSize);
info currNode;
currNode.size=left.size+right.size+1;
currNode.maxi=max(root->data,right.maxi);
currNode.mini=min(left.mini,root->data);
if(left.isBST && right.isBST && root->data>left.maxi && root->data<right.mini){
currNode.isBST=true;
}
else currNode.isBST=false;
if(currNode.isBST){
maxSize=max(maxSize,currNode.size);
}
return currNode;
}
int largestBst(Node *root)
{
//Your code here
int maxSize=0;
info temp=solve(root,maxSize);
return maxSize;
}
};