using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace _20170410_AOJ_ALDS1_8A
{
    class ALDS1_8A
    {
        static void Main(string[] args)
        {
            for (;;)
            {
                string line = Console.ReadLine();
                if (string.IsNullOrEmpty(line))
                {
                    break;
                }

                BinaryTree bt = new BinaryTree();
                int n = int.Parse(line);
                for(int i=0;i<n;i++)
                {
                    string[] command = Console.ReadLine().Split(' ');
                    int key;
                    switch (command[0])
                    {
                        case "delete":
                            key = int.Parse(command[1]);
                            bt.Delete(key);
                            break;
                        case "find":
                            key = int.Parse(command[1]);
                            TreeNode tn = bt.Find(key);
                            if(tn != null)
                            {
                                Console.WriteLine("yes");
                            }
                            else
                            {
                                Console.WriteLine("no");
                            }
                            break;
                        case "insert":
                            key = int.Parse(command[1]);
                            bt.Insert(key);
                            break;
                        case "print":
                            Console.Write(" ");
                            Console.WriteLine(string.Join(" ", bt.InOrder().Select(x => x.Key.ToString()).ToArray()));
                            Console.Write(" ");
                            Console.WriteLine(string.Join(" ", bt.PreOrder().Select(x => x.Key.ToString()).ToArray()));
                            break;
                    }
                }
            }
        }
    }

    class BinaryTree
    {
        List<TreeNode> list;
        public TreeNode Root { get { return GetRoot(); } }
        public BinaryTree()
        {
            list = new List<TreeNode>();
        }

        private TreeNode GetRoot()
        {
            if (list.Count == 0) return null;

            TreeNode temp = list[0];
            while (temp.Parent != null)
            {
                temp = temp.Parent;
            }

            return temp;
        }

        public void Delete(int key)
        {
            TreeNode tn = Find(key);
            Delete(tn);
        }

        void Delete(TreeNode tn)
        {
            if (tn == null) return;

            if (tn.Left == null && tn.Right == null)
            {
                if (tn.Parent.Left == tn)
                {
                    tn.Parent.Left = null;
                }
                else if (tn.Parent.Right == tn)
                {
                    tn.Parent.Right = null;
                }
                list.Remove(tn);
            }
            else if ((tn.Left == null) ^ (tn.Right == null))
            {
                TreeNode child = (tn.Left != null) ? tn.Left : tn.Right;
                if (tn.Parent.Left == tn)
                {
                    tn.Parent.Left = child;
                }
                else if (tn.Parent.Right == tn)
                {
                    tn.Parent.Right = child;
                }
                child.Parent = tn.Parent;
                list.Remove(tn);
            }
            else
            {
                List<TreeNode> rightTree = new List<TreeNode>();
                InOrder(rightTree, tn.Right);
                TreeNode nextNode = rightTree[0];
                tn.Key = nextNode.Key;
                Delete(nextNode);
            }
        }

        public TreeNode Find(int key)
        {
            return Find(Root, key);
        }

        static TreeNode Find(TreeNode tn, int key)
        {
            TreeNode rv = null;
            if (tn != null)
            {
                if (key < tn.Key)
                {
                    rv = Find(tn.Left, key);
                }
                else if (key > tn.Key)
                {
                    rv = Find(tn.Right, key);
                }
                else
                {
                    rv = tn;
                }
            }

            return rv;
        }

        public void Insert(int z)
        {
            TreeNode tn = new TreeNode();
            tn.Key = z;
            Insert(tn);
        }

        public void Insert(TreeNode z)
        {
            TreeNode y = null;
            TreeNode x = Root;
            
            while(x!=null)
            {
                y = x;
                x = (z.Key < x.Key) ? x.Left : x.Right;
            }

            z.Parent = y;

            list.Add(z);
            if(y==null)
            {
            }
            else if(z.Key < y.Key)
            {
                y.Left = z;
                z.Parent = y;
            }
            else
            {
                y.Right = z;
                z.Parent = y;
            }
        }

        public TreeNode[] PreOrder()
        {
            List<TreeNode> list = new List<TreeNode>();
            PreOrder(list, Root);
            return list.ToArray();
        }

        static void PreOrder(List<TreeNode> list, TreeNode tn)
        {
            list.Add(tn);

            if (tn.Left != null)
            {
                PreOrder(list, tn.Left);
            }

            if (tn.Right != null)
            {
                PreOrder(list, tn.Right);
            }
        }

        public TreeNode[] InOrder()
        {
            List<TreeNode> list = new List<TreeNode>();
            InOrder(list, Root);
            return list.ToArray();
        }

        static void InOrder(List<TreeNode> list, TreeNode tn)
        {
            if (tn.Left != null)
            {
                InOrder(list, tn.Left);
            }

            list.Add(tn);

            if (tn.Right != null)
            {
                InOrder(list, tn.Right);
            }
        }

        static void PostOrder(List<TreeNode> list, TreeNode tn)
        {
            if (tn.Left != null)
            {
                PostOrder(list, tn.Left);
            }

            if (tn.Right != null)
            {
                PostOrder(list, tn.Right);
            }

            list.Add(tn);
        }
    }

    class TreeNode
    {
        public int Key { get; set; }
        public TreeNode Parent { get; set; }
        public TreeNode Left { get; set; }
        public TreeNode Right { get; set; }
        public TreeNode()
        {
        }
    }
}



Measured memory_bytes: 77672