#include"iostream"
#include"vector"
using namespace std;
class branch
{
public:
  int key;
  branch *p;
  branch *left,*right;
  branch(){}
  branch(int key,branch *p)
  {
    this->key=key;
    this->p=p;
    this->left=NULL;
    this->right=NULL;
  }
};
branch *tree;
void insert(int z)
{
  branch *buf;
  branch *y=NULL;
  branch *x=tree;
  while(x!=NULL)
    {
      y=x;
      if(z<x->key)
        {
          x=x->left;
        }
      else
        {
          x=x->right;
        }
    }
  buf=new branch(z,y);
  if(y==NULL)tree=buf;
  else if(buf->key<y->key)y->left=buf;
  else y->right=buf;
}
branch* search(int key,branch *p)
{
  if(p==NULL)return NULL;
  if(p->key==key)return p;
  if(key<p->key)
    {
      return search(key,p->left);
    }
  else
    {
      return search(key,p->right);
    }
}
branch* find(int key)
{
  branch *p=tree;
  return search(key,p);
}
branch* getLeft(branch* p)
{
  if(p->left==NULL)return p;
  return getLeft(p->left);
}
void reDelete(branch *z)
{
  if(z->left==NULL&&z->right==NULL)
    {
      if(z->p->left!=NULL)
        {
          if(z->key==z->p->left->key)
            {
              z->p->left=NULL;
            }
        }
      if(z->p->right!=NULL)
        {
          if(z->key==z->p->right->key)
            {
              z->p->right=NULL;
            }
        }
    }
  else if(z->left==NULL)
    {
      if(z->p->left!=NULL)
        {
          if(z->key==z->p->left->key)
            {
              z->p->left=z->right;
              z->right->p=z->p;
            }
        }
      if(z->p->right!=NULL)
        {
          if(z->key==z->p->right->key)
            {
              z->p->right=z->right;
              z->right->p=z->p;
            }
        }
    }
  else if(z->right==NULL)
    {
      if(z->p->left!=NULL)
        {
          if(z->key==z->p->left->key)
            {
              z->p->left=z->left;
              z->left->p=z->p;
            }
        }
      if(z->p->right!=NULL)
        {
          if(z->key==z->p->right->key)
            {
              z->p->right=z->left;
              z->left->p=z->p;
            }
        }
    }
  else
    {
      if(z->p->left!=NULL)
        {
          if(z->key==z->p->left->key)
            {
              if(z->right->left==NULL)
                {
                  z->p->left=z->right;
                  z->right->p=z->p;
                  z->right->left=z->left;
                  z->left->p=z->right;
                }
              else
                {
                  branch *y=getLeft(z->right);
                  z->p->left=y;
                  y->p->left=y->right;
                  if(y->right!=NULL)y->right->p=y->p;
                  y->p=z->p;
                  y->right=z->right;
                  y->left=z->left;
                  z->left->p=y;
                }
            }
        }
      if(z->p->right!=NULL)
        {
          if(z->key==z->p->right->key)
            {
              if(z->right->left==NULL)
                {
                  z->p->right=z->right;
                  z->right->p=z->p;
                  z->right->left=z->left;
                  z->left->p=z->right;
                }
              else
                {
                  branch *y=getLeft(z->right);
                  z->p->right=y;
                  y->p->left=y->right;
                  if(y->right!=NULL)y->right->p=y->p;
                  y->p=z->p;
                  y->right=z->right;
                  y->left=z->left;
                  z->left->p=y;
                }
            }
        }
    }
}
void deleteBranch(int key)
{
  branch *z = find(key);
  if(z!=NULL)
    {
      reDelete(z);
    }
}
int preParse(branch *p)
{
  if(p==NULL)
    {
      return 0;
    }
  cout<<" "<<p->key;
  preParse(p->left);
  preParse(p->right);
}
int inParse(branch *p)
{
  if(p==NULL)
    {
      return 0;
    }
  inParse(p->left);
  cout<<" "<<p->key;
  inParse(p->right);
}
int postParse(branch *p)
{
  if(p==NULL)
    {
      return 0;
    }
  postParse(p->left);
  postParse(p->right);
  cout<<" "<<p->key;
}
int main()
{
  tree=NULL;
  int m;
  char cmd[20];
  cin>>m;
  for(int i=0;i<m;i++)
    {
      cin>>cmd;
      if(cmd[0]=='i')
        {
          int n;
          cin>>n;
          insert(n);
        }
      else if(cmd[0]=='p')
        {
          inParse(tree);
          cout<<endl;
          preParse(tree);
          cout<<endl;
        }
      else if(cmd[0]=='f')
        {
          int n;
          cin>>n;
          if(find(n)!=NULL)cout<<"yes"<<endl;
          else cout<<"no"<<endl;
        }
      else if(cmd[0]=='d')
        {
          int n;
          cin>>n;
          deleteBranch(n);
        }
    }
  return 0;
}


Measured memory_bytes: 21816