#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF = 1e9;

struct Node {
  int key_;
  Node *left_, *right_;
  Node *parent_;

  Node(int key) : key_(key), left_(0), right_(0) {}
  Node() : key_(0), left_(0), right_(0) {}
  ~Node()
  {
    if (left_) { delete left_; left_ = 0; }
    if (right_) { delete right_; right_ = 0; }
    parent_ = 0;
    //fprintf(stderr, "DEBUG: deleting %d\n", key_);
  }

  void print_inorder()
  {
    if (left_) { left_->print_inorder(); }
    fprintf(stdout, " %d", key_);
    if (right_) { right_->print_inorder(); }
  }

  void print_preorder()
  {
    fprintf(stdout, " %d", key_);
    if (left_) { left_->print_preorder(); }
    if (right_) { right_->print_preorder(); }
  }
};

class BST {
public:
  BST() : root_(0), size_(0) {}
  ~BST() { delete root_; }

  void insert(int key)
  {
    Node *node = new Node(key);
    Node *x = root_, *y = 0;
    while (x != 0) {
      y = x;
      if (node->key_ < x->key_) {
        x = x->left_;
      }
      else if (node->key_ > x->key_) {
        x = x->right_;
      }
      else {
        // duplicate node
        return;
      }
    }
    node->parent_ = y;

    if (y == 0) { root_ = node; }
    else if (node->key_ < y->key_) {
      y->left_ = node;
    }
    else if (node->key_ > y->key_) {
      y->right_ = node;
    }
    ++size_;
  }

  Node *find(int key)
  {
    Node *p = root_;
    while (p) {
      if (key == p->key_) { return p; }
      else if (key < p->key_) { p = p->left_; }
      else { p = p->right_; }
    }
    return 0;
  }

  void remove(int key)
  {
    Node *p = find(key);
    if (!p) { return; }
    if (p->left_ && p->right_) {
      Node *right_min = p->right_;
      while (right_min->left_) {
        right_min = right_min->left_;
      }
      p->key_ = right_min->key_;
      p = right_min;
    }
    Node *pp = p->parent_;
    if (p->left_) {
      p->left_->parent_ = pp;
      if (p == root_) { root_ = p->left_; }
      else if (p == pp->left_) { pp->left_ = p->left_; }
      else { pp->right_ = p->left_; }
    }
    else if (p->right_) {
      p->right_->parent_ = pp;
      if (p == root_) { root_ = p->right_; }
      else if (p == pp->left_) { pp->left_ = p->right_; }
      else { pp->right_ = p->right_; }
    }
    else {
      if (p == root_) { root_ = 0; }
      else if (p == pp->left_) { pp->left_ = 0; }
      else { pp->right_ = 0; }
    }
    p->left_ = p->right_ = 0;
    delete p;
    --size_;
  }

  void print_inorder()
  {
    if (root_) {
      root_->print_inorder();
      fprintf(stdout, "\n");
    }
  }

  void print_preorder()
  {
    if (root_) {
      root_->print_preorder();
      fprintf(stdout, "\n");
    }
  }

  int size() { return size_; }

private:
  Node *root_;
  int size_;
};

int main()
{
  int n = 0;
  fscanf(stdin, "%d", &n);
  char buf[64] = { '\0' };
  int key = -1;
  BST tree;
  for (int i = 0; i < n; ++i) {
    fscanf(stdin, "%s", buf);
    if (buf[0] == 'i') {
      fscanf(stdin, "%d", &key);
      tree.insert(key);
    }
    else if (buf[0] == 'p') {
      tree.print_inorder();
      tree.print_preorder();
    }
    else if (buf[0] == 'f') {
      fscanf(stdin, "%d", &key);
      if (tree.find(key)) {
        fprintf(stdout, "yes\n");
      }
      else {
        fprintf(stdout, "no\n");
      }
    }
    else if (buf[0] == 'd') {
      fscanf(stdin, "%d", &key);
      tree.remove(key);
      assert(!tree.find(key));
    }
  }
  return 0;
}

Measured memory_bytes: 19956