i am trying to solve https://open.kattis.com/problems/cookieselection. I am using kth smallest element in an sorted sequence using BST.But there is some bug and i am not able to figure out where.
#include <bits/stdc++.h>
#include<stdio.h>
using namespace std;
struct tree{
int val;
int sub;
tree* left;
tree* right;
tree(int x):val(x),left(NULL),right(NULL),sub(1){}
}roo;
tree findmin(tree* root,tree ** ro)
{
root->sub–;
if(root->left==NULL)
{
(ro)->val=root->val;
delete root;
root=NULL;
return root;
}
root->left=findmin(root->left,ro);
}
tree insert(int value,tree* root)
{
if(root==NULL)
{
root=new tree(value);
return root;
}
(root->sub)++;
if(root->val>=value)
{
root->left=insert(value,root->left);
}
else
{
root->right=insert(value,root->right);
}
}
tree* delet(tree* root,int k)
{
int a;
if(root->left==NULL)
a=0;
else
a=root->left->sub;
//cout<val<<" ";
if(a==k-1)
{
if(root->left==NULL && root->right==NULL)
{
int ans=root->val;
cout<<ans<<endl;
delete root;
root=NULL;
}
else if(root->left==NULL)
{
int ans=root->val;
cout<<ans<<endl;
tree* temp=root;
root=root->right;
delete temp;
}
else if(root->right==NULL)
{
int ans=root->val;
cout<<ans<<endl;
tree*temp=root;
root=root->left;
delete temp;
}
else
{
int ans=root->val;
root->right=findmin(root->right,&root);
root->sub--;
cout<<ans<<endl;
}
return root;
}
else if(a>k-1)
{
root->sub--;
root->left=delet(root->left,k);
}
else
{
root->sub--;
root->right=delet(root->right,k-a - 1);
}
}
int main()
{
char d;
roo=NULL;
int size=0,ans;
while(cin>>d)
{
if(d==‘#’)
{
if(size%2==0)
roo=delet(roo,size/2 + 1);
else
roo=delet(roo,(size+1)/2);
size–;
}
else
{
roo=insert(int(d) - 48,roo);
size++;
}
}
return 0;
}