
class Tree
	attr_reader :key
	attr_accessor :left, :right
	def initialize key
		@key = key
		@left = nil
		@right = nil
	end

	def insert k
		if @key > k
			if !@left
				@left = Tree.new k
			else
				@left.insert(k)
			end

		else
			if !@right
				@right = Tree.new k
			else
				@right.insert k
			end
		end
	end

	def inorder list
		if @left
			list = @left.inorder list
		end
		list << @key
		if @right
			list = @right.inorder list
		end
		list
	end

	def preorder list
		list << @key
		if @left
			list = @left.preorder list
		end
		if @right
			list = @right.preorder list
		end
		list
	end

	def find key
		if @key == key
			key
		else
			bool = nil
			if @left && @key > key
				bool = @left.find key
			end

			if @right && @key < key
				bool = @right.find key
			end
			bool
		end
	end

	def delete k
		parent = traverse(k)
		child = parent.left.key == k ? parent.left : parent.right if parent

		if child
			if child.left && child.right 
				if parent.left.key == k
					parent.left = child.left
				else
					parent.right = child.left
				end
				child.left.right = child.right

			elsif child.left
				if parent.left.key == k
					parent.left = child.left
				else
					parent.right = child.left
				end

			elsif child.right
				if parent.left.key == k
					parent.left = child.right
				else
					parent.right = child.right
				end

			else
				if parent.left.key == k
					parent.left = nil
				else
					parent.right = nil
				end
			end
		end
	end

	def traverse k
		if (@left && @left.key == k) || (@right && @right.key == k)
			self
		else
			tree = nil
			tree = @left.traverse k if @left
			tree = @right.traverse k if @right
			tree
		end
	end
end
n = gets.to_i
head = nil

n.times do
	num = gets.to_s.chomp!
	if num == "print"
		puts " #{head.inorder([]).join(" ")}"
		puts " #{head.preorder([]).join(" ")}"
	else
		num = num.split
		if num[0].to_s == "insert"
			if head
				head.insert(num[1].to_i)
			else
				head = Tree.new(num[1].to_i)
			end
		elsif num[0].to_s == "delete"
			head.delete num[1].to_i 
		else
			puts head.find(num[1].to_i) ?  "yes" : "no"
		end

	end

end