using System;
using System.Collections.Generic;

namespace ConsoleApplication1
{    

    class Node
    {
        public long? key = null;
        public Node left;
        public Node right;
        public Node parent;
    }

    class Program
    {       
        static Node root;
        static Node u;
        static Node p;
        static Node x;

        static void Insert(long k)
        {         
            u = root;

            while(true)
            {
                if(k < u.key)
                {
                    if(u.left == null)
                    {
                        Node newnode = new Node();
                        u.left = newnode;
                        newnode.key = k;
                        newnode.parent = u;                       
                        break;
                    }
                    else
                    {
                        u = u.left;
                    }                 
                }
                else if(k > u.key)
                {
                    if(u.right == null)
                    {
                        Node newnode = new Node();
                        u.right = newnode;
                        newnode.key = k;
                        newnode.parent = u;                       
                        break;
                    }
                    else
                    {
                        u = u.right;
                    }                  
                }
            }
           
            return;
        }


        static void Delete(long key)
        {
            Find(key); 

            x = u;
            p = u.parent;
            
            //rootを削除
            if (u.key == root.key)
            {
                //両方なし
                if(x.left == null && x.right == null)
                {
                    root.key = null;
                }
                //右なし
                else if(x.right == null)
                {
                    root.left.parent = null;
                    root = root.left;        
                }
                //左なし
                else if(x.left == null)
                {
                    root.right.parent = null;
                    root = root.right;
                }
                //rootが2つNodeもち
                else
                {
                    u = root.right;

                    if (u.left == null)
                    {
                        u.left = root.left;
                        root.left.parent = u;
                        root = u;
                        u.parent = null;
                    }

                    else
                    {
                        while (true)
                        {
                            if (u.left == null)
                            {
                                break;
                            }
                            u = u.left;
                        }

                        u.parent.left = null;
                        u.left = root.left;
                        root.left.parent = u;                    
                        u.parent = null;
                        u.right = root.right;
                        root.right.parent = u;
                        root = u;
                    }

                }
                

            }

            //root以外のNodeを削除
            else
            {
                if (x.left == null && x.right == null)
                {                 
                    if (p.left != null && p.left.key == x.key)
                    {
                        p.left = null;
                    }
                    else
                    {
                        p.right = null;
                    }
                }

                //削除対象が1つのNode持ち（右なし）
                else if (x.right == null)
                {
                   
                    if (p.left != null && p.left.key == x.key)
                    {                        
                        u = x.left;
                        u.parent = p;
                        p.left = u;
                    }
                    else
                    {
                        u = x.left;
                        u.parent = p;
                        p.right = u;
                    }

                }

                //削除対象が1つのNode持ち（左なし）
                else if (x.left == null)
                {                   
                    u = x.right;
                    u.parent = p;                   

                    if (p.left != null && p.left.key == x.key)
                    {
                        p.left = u;
                    }
                    else
                    {
                        p.right = u;
                    }
                }

                //削除対象が2つのNodeを持つ
                else
                {                   
                    u = x.right;

                    if (u.left == null)
                    {                      
                        if (p.left != null && p.left.key == x.key)
                        {
                            p.left = u;
                        }
                        else
                        {                         
                            p.right = u;
                        }
                        u.parent = p;
                        u.left = x.left;                                           

                    }

                    else
                    {
                        while (true)
                        {
                            if (u.left == null)
                            {
                                break;
                            }
                            u = u.left;
                        }

                        if (p.left != null && p.left.key == x.key)
                        {
                            p.left = u;
                        }
                        else
                        {
                            p.right = u;
                        }
                        u.parent.left = null;
                        u.parent = p;
                        u.right = x.right;
                        u.left = x.left;
                        x.left.parent = u;
                        u.right.parent = u;
                    }

                }
            }

            
        }


        static bool Find(long k)
        {
            u = root;

            while (true)
            {               
                if (u.key == k)
                {
                    return true;
                }

                if (k < u.key)
                {
                    if (u.left == null)
                    {                       
                        return false;
                    }
                    else
                    {                       
                        u = u.left;
                    }
                }
                else if (k > u.key)
                {
                    if (u.right == null)
                    {
                        return false;
                    }
                    else
                    {
                        u = u.right;
                    }
                }
                
            }

        }

        static void Pre(Node u)
        {
            if(u == null)
            {
                return;
            }
            Console.Write(" " + u.key);            
            Pre(u.left);
            Pre(u.right);
        }

        static void Ino(Node u)
        {
            if(u == null)
            {
                return;
            }
            Ino(u.left);
            Console.Write(" " + u.key);           
            Ino(u.right);
        }
        
        
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            string[] input;
            string order;
            long key;

            u = new Node();

            for (int i = 0; i < n; i++)
            {
                input = Console.ReadLine().Split(' ');
                order = input[0];

                if(order == "insert")
                {
                    key = long.Parse(input[1]);
                    if(i == 0)
                    {
                        root = new Node();
                        root.key = key;
                        root.left = null;
                        root.right = null;
                    }
                    else
                    {
                        Insert(key);
                    }                 
                }
                else if(order == "print")
                {
                    Ino(root);
                    Console.WriteLine();
                    Pre(root);
                    Console.WriteLine();
                }
                else if(order == "find")
                {
                    key = long.Parse(input[1]);
                    if (Find(key))
                    {
                        Console.WriteLine("yes");
                    }
                    else
                    {
                        Console.WriteLine("no");
                    }
                }
                else if(order == "delete")
                {

                    key = long.Parse(input[1]);

                    Delete(key);
                }
            }
        }
    }
}



Measured memory_bytes: 42368