please help, almost done but getting output as 1 instead of 2 for input test case
#include <bits/stdc++.h>
using namespace std;
class node{
public:
int data;
node* left;
node* right;
node(int d){
data=d;
left=NULL;
right=NULL;
}
};
class GetMaxBST{
public:
int ans;
int mini;
int maxi;
int size;
bool isBST;
};
//following a bottom up approach
GetMaxBST getmaxbst(node* root){
if(root==NULL){
return {0, INT_MIN, INT_MAX, 0, true};
}
if(root->left == NULL && root->right == NULL){
//leaf node
return {1, root->data, root->data, 1, true};
}
GetMaxBST left=getmaxbst(root->left);
GetMaxBST right=getmaxbst(root->right);
GetMaxBST b;
b.size=1+left.size+right.size;
if(left.maxi < root->data && right.mini > root->data && left.isBST && right.isBST){
b.ans=b.size;
b.isBST=true;
b.mini = min(left.mini, root->data);
b.maxi = max(right.maxi, root->data);
return b;
}
node* create_tree_from_pre_and_inorder(int* ino,int* pre,int s,int e,unordered_map <int,int >mp){
if(s>e){
return NULL;
}
//wont be assigned again and again so we use static here.
static int i=0;
int index=-1;
node* root=new node(pre[i]);
//takes O(1) time to search using hashing
index=mp[pre[i]];
i++;
root->left=create_tree_from_pre_and_inorder(ino,pre,s,index-1,mp);
root->right=create_tree_from_pre_and_inorder(ino,pre,index+1,e,mp);
return root;
}
int main() {
int n;
cin>>n;
unordered_map<int,int>mp;
int pre[n],ino[n];
for(int i=0;i<n;i++){
cin>>pre[i];
}
//hashing used to save time in searching
for(int i=0;i<n;i++){
cin>>ino[i];
mp[ino[i]]=i;
}
node* root=create_tree_from_pre_and_inorder(ino,pre,0,n-1,mp);
cout<<getmaxbst(root).ans<<endl;
return 0;
}