#include <iostream>
using namespace  std;

struct StNode
{
  StNode* m_poParnt;
  StNode* m_poLeft;
  StNode* m_poRigt;
  int m_nKey;

  StNode(int nNo) :
    m_poParnt(nullptr), m_poLeft(nullptr), m_poRigt(nullptr), m_nKey(nNo)
  { }
};

void fnInsert(StNode*& rpoRoot, StNode* poNewNod)
{
  StNode* poParnt = nullptr;
  StNode* poNode = rpoRoot;

  while (poNode)
  {
    poParnt = poNode;
    if (poNewNod->m_nKey < poNode->m_nKey)
      poNode = poNode->m_poLeft;
    else
      poNode = poNode->m_poRigt;
  }

  poNewNod->m_poParnt = poParnt;
  if (!poParnt)
    rpoRoot = poNewNod;
  else if (poNewNod->m_nKey < poParnt->m_nKey)
    poParnt->m_poLeft = poNewNod;
  else
    poParnt->m_poRigt = poNewNod;
}

StNode* fnFind(StNode* poRoot, int nNo)
{
  StNode* poNode = poRoot;
  while (poNode)
    if (nNo == poNode->m_nKey)
      return poNode;
    else if (nNo < poNode->m_nKey)
      poNode = poNode->m_poLeft;
    else
      poNode = poNode->m_poRigt;

  return nullptr;
}

void fnDelete(StNode*& rpoRoot, StNode* poNode)
{
  if (!poNode)  return;

  StNode** ppoPrToMe;
  if (poNode == rpoRoot)
    ppoPrToMe = &rpoRoot;
  else
    if (poNode->m_nKey < poNode->m_poParnt->m_nKey)
      ppoPrToMe = &poNode->m_poParnt->m_poLeft;
    else
      ppoPrToMe = &poNode->m_poParnt->m_poRigt;

  int nDegr = 0;
  StNode* poMeToCd = nullptr;
  if (poNode->m_poLeft)
  {
    ++nDegr;
    poMeToCd = poNode->m_poLeft;
  }
  if (poNode->m_poRigt)
  {
    ++nDegr;
    poMeToCd = poNode->m_poRigt;
  }

  if (!nDegr)
  {
    *ppoPrToMe = poMeToCd;
    delete poNode;
  }
  else if (nDegr == 1)
  {
    if (poNode != rpoRoot)
      poMeToCd->m_poParnt = poNode->m_poParnt; 
    else;
    *ppoPrToMe = poMeToCd;
    delete poNode;
  }
  else if (nDegr == 2)
  {
    StNode* poNext = poNode->m_poRigt;
    while (poNext->m_poLeft )
      poNext = poNext->m_poLeft;

    poNode->m_nKey = poNext->m_nKey;
    fnDelete(rpoRoot, poNext);
  }
}

void fnInOrder(StNode* poNode)
{
  if (!poNode)  return;

  fnInOrder(poNode->m_poLeft);
  cout << " " << poNode->m_nKey;
  fnInOrder(poNode->m_poRigt);
}

void fnPreOrder(StNode* poNode)
{
  if (!poNode)  return;

  cout << " " << poNode->m_nKey;
  fnPreOrder(poNode->m_poLeft);
  fnPreOrder(poNode->m_poRigt);
}

void fnBinSchTree(StNode*& rpoRoot)
{
  int nMaxSiz;
  cin >> nMaxSiz;

  for (int i = 0; i < nMaxSiz; ++i)
  {
    string sCmd;
    cin >> sCmd;
    if (sCmd[0] == 'i')
    {
      int nNo;
      cin >> nNo;
      StNode* poNewNod = new StNode(nNo);
      fnInsert(rpoRoot, poNewNod);
    }
    else if (sCmd[0] == 'f')
    {
      int nNo;
      cin >> nNo;
      if (fnFind(rpoRoot, nNo))
        cout << "yes" << endl;
      else
        cout << "no" << endl;
    }
    else if (sCmd[0] == 'd')
    {
      int nNo;
      cin >> nNo;
      StNode* poNode;
      if (poNode = fnFind(rpoRoot, nNo))
        fnDelete(rpoRoot, poNode);
      else;
    }
    else if (sCmd[0] == 'p')
    {
      fnInOrder(rpoRoot);
      cout << endl;
      fnPreOrder(rpoRoot);
      cout << endl;
    }
    else;
  }
}

void fnPstOrder(StNode* poNode)
{
  if (!poNode)  return;

  fnPstOrder(poNode->m_poLeft);
  fnPstOrder(poNode->m_poRigt);
  delete poNode;
}

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  StNode* poRoot = nullptr;

  fnBinSchTree(poRoot);
  fnPstOrder(poRoot);
  return 0;
}

Measured memory_bytes: 21952