I am conistantly getting WA’s and I cannot figure out what is wrong witth my solution …? Also can u prvoide me edgy test cases…
Here is my code.
#include
#include <stdio.h>
#define null NULL
using namespace std ;
int max1(int a,int b)
{
if(a>b) return a;
return b;
}
struct node
{
struct node *l,*r ;
int val ;
int nl,nr ;
int height;
};
struct node *root ;
struct node *new_node(int val)
{
struct node *temp=new struct node ;
temp->val=val;
temp->l= NULL;
temp->r= null;
temp->height=1;
temp->nl=0;
temp->nr=0;
return temp;
}
int height(struct node *temp)
{
if(temp== null) return 0;
else return temp->height ;
}
int getbal(struct node *temp)
{
if(temp==null) return 0;
return height(temp->r) - height(temp->l);
}
int nl1(struct node *temp)
{
if(temp==null ) return 0;
return temp->nl;
}
int nr1(struct node *temp)
{
if(temp==null ) return 0;
return temp->nr;
}
int val(struct node *temp)
{
if(temp==null) return 0;
return temp->val;
}
int nl(struct node *temp)
{
if(temp==null) return 0;
return nl1(temp)+nr1(temp)+1;
}
int nr(struct node *temp)
{
if(temp==null) return 0;
return nl1(temp)+nr1(temp)+1;
}
struct node *lr(struct node *temp)
{
struct node *x=temp->r;
struct node *b=x->l;
x->l=temp;
temp->r=b;
temp->height=max(height(temp->l),height(temp->r))+1;
x->height=max(height(x->l),height(x->r))+1;
temp->nl=nl(temp->l);
temp->nr=nr(temp->r);
x->nl=nl(x->l);
x->nr=nr(x->r);
}
struct node *rr(struct node *temp)
{
struct node *x=temp->l;
struct node *b=x->r;
x->r=temp;
temp->l=b;
temp->height=max(height(temp->l),height(temp->r))+1;
x->height=max(height(x->l),height(x->r))+1;
temp->nl=nl(temp->l);
temp->nr=nr(temp->r);
x->nl=nl(x->l);
x->nr=nr(x->r);
}
int find(struct node *temp,int val)
{
int x;
if(temp==null)
{
return -1;
}
if(temp->val == val )
{
return temp->nl;
}
else if(temp->val < val)
{
x=find(temp->r,val);
if(x==-1) return -1;
else return x+ nl1(temp) +1;
}
else
{
x=find(temp->l,val);
if(x==-1) return -1 ;
else return x ;
}
}
struct node * insert(int val,struct node *temp)
{
if(temp==null)
{
temp=new_node(val);
return temp ;
}
if(val < temp->val)
{
temp->nl++;
temp->l=insert(val,temp->l);
}
else
{
temp->nr++;
temp->r=insert(val,temp->r);
}
temp->height= 1 + max(height(temp->l),height(temp->r));
int balance = getbal(temp);
if(balance >1 && val > temp->r->val)
return lr(temp);
if(balance >1 && val < temp->r->val)
{
temp->r=rr(temp->r);
return lr(temp);
}
if(balance <-1 && val < temp->l->val)
{
return rr(temp);
}
if(balance <-1 && val > temp->l->val)
{
temp->l=lr(temp->l);
return rr(temp);
}
return temp ;
}
void solve()
{
struct node *temp=root;
int x,y ;
scanf("%d%d",&x,&y);
if(x==1)
{
root = insert(y,temp);
}
else
{
int m= find(temp,y);
if(m==-1)
printf("Data tidak ada\n");
else
printf("%d\n",m+1);
}
}
int main()
{
root=null;
int a;
scanf("%d",&a);
while(a--) solve();
}