#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <climits>

struct Node {
  struct Node *right;
  struct Node *left;
  struct Node *parent;
  int key;
};

struct Node *insertNode(struct Node *root, int k){
  struct Node *y = NULL;
  struct Node *x = root;
  struct Node *newNode;

  newNode = (struct Node *) std::malloc(sizeof(struct Node));
  
  newNode->right = NULL;
  newNode->left = NULL;
  newNode->parent = NULL;
  newNode->key = k;

  while (x != NULL) {
    y = x;
    
    if (newNode->key < x->key) {
      x = x->left;
    } else {
      x = x->right;
    }
  }

  newNode->parent = y;

  if (y == NULL) {
    root = newNode;
  } else if (newNode->key < y->key) {
    y->left = newNode;
  } else {
    y->right = newNode;
  }

  return root;
}

void printByInorder(struct Node *root) {
  if (root == NULL) {
    return;
  }

  if ((root->left == NULL) && (root->right == NULL)) {
    std::cout << " " << root->key;
    return;
  }

  printByInorder(root->left);
  std::cout << " " << root->key;
  printByInorder(root->right);
}

void printByPreorder(struct Node *root) {
  if (root == NULL) {
    return;
  }

  if ((root->left == NULL) && (root->right == NULL)) {
    std::cout << " " << root->key;
    return;
  }
  
  std::cout << " " << root->key;
  printByPreorder(root->left);
  printByPreorder(root->right);
}

bool find_value(struct Node* root, int v) {
  if (root == NULL) {
    return false;
  }

  struct Node *node = root;

  while (node != NULL) {
    if (node->key == v) {
      return true;
    }
    
    if (node->key < v) {
      node = node->right;
    } else {
      node = node->left;
    }
  }

  return false;
}

int next_print_value(struct Node *root) {
  if (root == NULL) {
    return INT_MAX;
  }

  if ((root->left == NULL) && (root->right == NULL)) {
    return root->key;
  }

  int v = next_print_value(root->left);

  if (v != INT_MAX) {
    return v;
  }

  return root->key;
}

void delete_value(struct  Node *root, int v) {
  if (root == NULL) {
    return;
  }

  struct Node *node = root;

  while (node != NULL) {
    if (node->key == v) {
      break;
    }
    
    if (node->key < v) {
      node = node->right;
    } else {
      node = node->left;
    }
  }

  if (node == NULL) {
    return;
  }

  if ((node->left == NULL) && (node->right == NULL)) {
    if (node == node->parent->left) {
      node->parent->left = NULL;
    } else {
      node->parent->right = NULL;
    }
  } else if ((node->left != NULL) && (node->right == NULL)) {
    if (node == node->parent->left) {
      node->parent->left = node->left;
    } else {
      node->parent->right = node->left;
    }

    node->left->parent = node->parent;    
  } else if ((node->left == NULL) && (node->right != NULL)) {
    if (node == node->parent->left) {
      node->parent->left = node->right;
    } else {
      node->parent->right = node->right;
    }

    node->right->parent = node->parent;
  } else {
    int k = next_print_value(node->right);

    delete_value(node, k);

    node->key = k;
  }
}

int main(){
  int n = 0;
  struct Node *root = NULL;

  std::cin >> n;

  for (int i = 0; i < n; i++) {
    std::string command;
    
    std::cin >> command;
    
    if (command.at(0) == 'p') {
      printByInorder(root);
      std::cout << std::endl;

      printByPreorder(root);
      std::cout << std::endl;
    } else if (command.at(0) == 'i') {
      int k = 0;

      std::cin >> k;
      
      root = insertNode(root, k);
    } else if (command.at(0) == 'f') {
      int v = 0;

      std::cin >> v;
      
      if (find_value(root, v)) {
	std::cout << "yes";
      } else {
	std::cout << "no";
      }

      std::cout << std::endl;
    } else if (command.at(0) == 'd') {
      int v = 0;

      std::cin >> v;

      delete_value(root, v);
    }
  }

  return 0;
}

Measured memory_bytes: 19956