import scala.io.StdIn.{readInt, readLine};
import scala.annotation.tailrec;

object Main {
    def main(args: Array[String]): Unit = {
        val cnt = readInt;
        val binTree = new BinaryTree[Long,Boolean]((k1, k2) => if (k1 < k2) -1 else if (k1 > k2) 1 else 0);
        (0 until cnt).foreach { i =>
            readLine.split(" ") match {
                case Array("insert", key) => binTree.insert(key.toLong, true);
                case Array("find", key) => if (binTree.find(key.toLong) != None) println("yes") else println("no");
                case Array("delete", key) => binTree.delete(key.toLong);
                case Array("print") => {
                    println(" " + binTree.fetchInorder.map(_._1).mkString(" "));
                    println(" " + binTree.fetchPreoder.map(_._1).mkString(" "));
                }
            }
        }
    }
}
class BinaryTree[A,B](val compare: (A,A) => Int) {
    case class TreeNode(var key: Option[A], var value: Option[B], var parent: TreeNode, var left: TreeNode, var right: TreeNode);
    var tree: TreeNode = TreeNode(None, None, null, null, null);
    
    def isEmpty(): Boolean = if (tree.right == null) true else false;
    
    // 要素を登録する
    def insert(key: A, value: B): Unit = {
        @tailrec
        def _insert(curr: TreeNode): Unit = {
            if (compare(key, curr.key.get) < 0) { // 追加対象ノードのほうが小さい
                if (curr.left == null) {
                    curr.left = TreeNode(Some(key), Some(value), curr, null, null);
                } else {
                    _insert(curr.left);
                }
            } else if (compare(key, curr.key.get) > 0) { // 追加対象ノードのほうが大きい
                if (curr.right == null) {
                    curr.right = TreeNode(Some(key), Some(value), curr, null, null);
                } else {
                    _insert(curr.right);
                }
            }
        }
        isEmpty match {
            case true => tree.right = TreeNode(Some(key), Some(value),null, null, null);
            case false => _insert(tree.right);
        }
    }
    
    // key を探索する
    private def findSub(key: A): Option[TreeNode] = {
        @tailrec
        def _findSub(curr: TreeNode): Option[TreeNode] = curr match {
            case null => None;
            case node if compare(key, node.key.get) < 0 => _findSub(node.left);
            case node if compare(key, node.key.get) > 0 => _findSub(node.right);
            case node => Some(node);
        }
        _findSub(tree.right);
    }
    
    def find(key: A): Option[B] = {
        findSub(key) match {
            case None => None;
            case Some(node) => node.value;
        }
    }
    
    def delete(key: A): Unit = {
        // 部分木の中から最小のノードを返す。
        def getMinNode(curr: TreeNode): TreeNode = if (curr.left == null) curr else getMinNode(curr.left);
        def _delete(curr: TreeNode): Unit = {
            if (curr.left == null && curr.right == null) {
                if (curr.parent.left == curr) curr.parent.left = null else curr.parent.right = null;
            } else if (curr.left == null) {
                curr.right.parent = curr.parent;
                if (curr.parent.left == curr) curr.parent.left = curr.right else curr.parent.right = curr.right;
            } else if (curr.right == null) {
                curr.left.parent = curr.parent;
                if (curr.parent.left == curr) curr.parent.left = curr.left else curr.parent.right = curr.left;
            } else {
                val min = getMinNode(curr.right);
                curr.key = min.key;
                curr.value = min.value;
                _delete(min);
            }
        }
        val target = findSub(key);
        if (target != None) _delete(target.get);
    }

    // 先行巡回で要素を返す
    def fetchPreoder(): List[(A, B)] = {
        def _fetchPreoder(curr: TreeNode, ret: List[(A, B)]): List[(A, B)] = {
            if (curr == null) {
                ret;
            } else {
                val ret1 = (curr.key.get, curr.value.get) :: ret;
                val ret2 = _fetchPreoder(curr.left, ret1);
                val ret3 = _fetchPreoder(curr.right, ret2);
                ret3;
            }
        }
        _fetchPreoder(tree.right, Nil).reverse;
    }
    
    // 中間巡回で要素を返す
    def fetchInorder(): List[(A, B)] = {
        def _fetchInorder(curr: TreeNode, ret: List[(A, B)]): List[(A, B)] = {
            if (curr == null) {
                ret;
            } else {
                val ret1 = _fetchInorder(curr.left, ret);
                val ret2 = (curr.key.get, curr.value.get) :: ret1;
                val ret3 = _fetchInorder(curr.right, ret2);
                ret3;
            }
        }
        _fetchInorder(tree.right, Nil).reverse;
    }
}


Measured memory_bytes: 514556