Problem:
Binary Search Tree III Write a program which performs the following operations to a binary search tree $T$ by adding delete operation to B: Binary Search Tree II.  insert $k$: Insert a node containing $k$ as key into $T$.  find $k$: Report whether $T$ has a node containing $k$.  delete $k$: Delete a node containing $k$.  print : Print the keys of the binary search tree by inorder tree walk and  preorder tree walk respectively.  The operation delete $k$ for deleting a given node $z$ containing key $k$ from $T$ can be implemented by an algorithm which considers the following cases:  If $z$ has no children, we modify its parent $z.p$ to replace $z$ with NIL as its child (delete $z$).  If $z$ has only a single child, we "splice out" $z$ by making a new link between its child and its parent.  If $z$ has two children, we splice out $z$'s successor $y$ and replace $z$'s key with $y$'s key.  Input In the first line, the number of operations $m$ is given. In the following $m$ lines, operations represented by insert $k$, find $k$, delete $k$ or print are given. Output For each find $k$ operation, print " yes " if $T$ has a node containing $k$, " no " if not. In addition, for each print operation, print a list of keys obtained by inorder tree walk and preorder tree walk in a line respectively. Put a space character before each key  Constraints   The number of operations $\leq 500,000$  The number of print operations $\leq 10$.  $-2,000,000,000 \leq key \leq 2,000,000,000$  The height of the binary tree does not exceed 100 if you employ the above pseudo code.  The keys in the binary search tree are all different.   Sample Input 1  18
insert 8
insert 2
insert 3
insert 7
insert 22
insert 1
find 1
find 2
find 3
find 4
find 5
find 6
find 7
find 8
print
delete 3
delete 7
print  Sample Output 1  yes
yes
yes
no
no
no
yes
yes
 1 2 3 7 8 22
 8 2 1 3 7 22
 1 2 8 22
 8 2 1 22  Reference  Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. The MIT Press.

Solution (Python):
class Tree:
    root = None

    def insert(self, node):
        y = None
        x = self.root
        while x:
            y = x
            x = x.left if node.key < x.key else x.right
        node.parent = y

        if not y:
            self.root = node
        elif node.key < y.key:
            y.left = node
        else:
            y.right = node

    def find_node(self, value):
        return self.root.find(value)

    def find(self, value):
        print('yes' if self.find_node(value) else 'no')

    def delete(self, value):
        self.find_node(value).delete()

    def print(self):
        print(' ', end='')
        print(*self.root.print_in())
        print(' ', end='')
        print(*self.root.print_pre())


class Node:
    def __init__(self, key):
        self.parent = self.left = self.right = None
        self.key = key

    def find(self, value):
        diff = self.key - value
        if diff == 0:
            return self
        elif diff > 0:
            return self.left and self.left.find(value)
        else:
            return self.right and self.right.find(value)

    def delete(self):
        left, right = self.left, self.right
        if not left and not right:
            self.delete_connect(self.parent, None)
        elif left and not right:
            self.delete_connect(self.parent, left)
        elif not left and right:
            self.delete_connect(self.parent, right)
        else:
            next_node = right.get_leftmost()
            self.key = next_node.key
            next_node.delete()

    def delete_connect(self, parent, child):
        if parent:
            if parent.key > self.key:
                parent.left = child
            else:
                parent.right = child
        if child:
            child.parent = parent

    def get_leftmost(self):
        if self.left:
            return self.left.get_leftmost()
        return self

    def print_pre(self):
        yield self.key
        if self.left:
            for k in self.left.print_pre(): yield k
        if self.right:
            for k in self.right.print_pre(): yield k

    def print_in(self):
        if self.left:
            for k in self.left.print_in(): yield k
        yield self.key
        if self.right:
            for k in self.right.print_in(): yield k


tree = Tree()
m = int(input())

while m:
    l = input()
    f = l[0]
    if f == 'i':
        tree.insert(Node(int(l.split()[1])))
    elif f == 'f':
        tree.find(int(l.split()[1]))
    elif f == 'd':
        tree.delete(int(l.split()[1]))
    else:
        tree.print()
    m -= 1

Solution (Python):

from __future__ import division, print_function
from sys import stdin
   
   
class Node(object):
    def __init__(self, key=None):
        self.key = key
        self.parent = None
        self.left = None
        self.right = None
   
   
def tree_insert(top, z):
    y = None
    x = top
    while isinstance(x, Node):
        y = x
        if z.key < x.key:
            x = x.left
        else:
            x = x.right
    z.parent = y
    if y is None:
        top = z
    elif z.key < y.key:
        y.left = z
    else:
        y.right = z
    return top
   
def tree_find(top, k):
    x = top
    while x != None and k != x.key:
        if k < x.key:
            x = x.left
        else:
            x = x.right
    return x

def deleteNode(top, z):
    if z.left == None or z.right == None:
        y = z
    else:
        y = getSuccessor(z)

    if y.left != None:
        x = y.left
    else:
        x = y.right

    if x != None:
        x.parent = y.parent

    if y.parent == None:
        top = x
    elif y == y.parent.left:
        y.parent.left = x
    else:
        y.parent.right = x

    if y != z:
        z.key = y.key
    return top

def getSuccessor(x):
    if x.right != None:
        return getMinimum(x.right)

    y = x.parent
    while y != None and x == y.right:
        x = y
        y = y.parent
    return y

def getMinimum(x):
    while x.left != None:
        x = x.left
    return x


def inorder_walk(node):
    if node.left:
        inorder_walk(node.left)
    print('', node.key, end='')
    if node.right:
        inorder_walk(node.right)
   
   
def preorder_walk(node):
    print('', node.key, end='')
    if node.left:
        preorder_walk(node.left)
    if node.right:
        preorder_walk(node.right)
   
   
n = int(stdin.readline())
   
top = None
for _ in range(n):
    cmd = stdin.readline()
    if cmd.startswith('i'):
        key = int(cmd[7:])
        
        top = tree_insert(top, Node(key))
    elif cmd.startswith('f'):
        key = int(cmd[5:])
        if tree_find(top, key) != None:
            print('yes')
        else:
            print('no')
    elif cmd.startswith('d'):
        key = int(cmd[7:])
        top = deleteNode(top, tree_find(top, key))
    else:
        inorder_walk(top)
        print()
        preorder_walk(top)
        print()

Solution (Python):
class BinarySearchTree:
    root = None
    def insert(self, k):
        y = None
        x = self.root
        z = Node(k)
        while x:
            y = x
            if z.k < x.k:
                x = x.l
            else:
                x = x.r
        z.p = y
         
        if y == None:
            self.root = z
        else:
            if z.k < y.k:
                y.l = z
            else:
                y.r = z
                
    def find(self, x, k):
        while x != None and k != x.k:
            if k < x.k:
                x = x.l
            else:
                x = x.r
        return x
     
    def deleteNode(self, z):
        y = None
        x = None
        if z.l == None or z.r == None:
            y = z
        else:
            y = self.getSuccessor(z)
        
        if y.l != None:
            x = y.l
        else:
            x = y.r
        
        if x != None:
            x.p = y.p
        
        if y.p == None:
            self.root = x
        else:
            if y == y.p.l:
                y.p.l = x
            else:
                y.p.r = x
        
        if y != z:
            z.k = y.k

    def getSuccessor(self, x):
        if x.r != None:
            return self.getMinimum(x.r)
        y = x.p
        while y != None and x == y.r:
            x = y
            y = y.p
        return y
    
    def getMinimum(self, x):
        while x.l != None:
            x = x.l
        return x
    
    def preParse(self, u):
        if u == None:
            return
        print("", str(u.k), end = "")
        self.preParse(u.l)
        self.preParse(u.r)
 
    def inParse(self, u):
        if u == None:
            return
        self.inParse(u.l)
        print("", str(u.k), end = "")
        self.inParse(u.r)
 
class Node: 
    def __init__(self, k):
        self.k = k
        self.p = None
        self.l = None
        self.r = None
 
if __name__ == '__main__':
    n = int(input().rstrip())
    x = BinarySearchTree()
    for i in range(n):
        com = input().rstrip()
        if com.startswith("insert"):
            k = int(com.split(" ")[1])
            x.insert(k)
        elif com.startswith("find"):
            k = int(com.split(" ")[1])
            if x.find(x.root, k) != None:
                print("yes")
            else:
                print("no")
        elif com.startswith("delete"):
            k = int(com.split(" ")[1])
            x.deleteNode(x.find(x.root, k))
        else:
            x.inParse(x.root)
            print()
            x.preParse(x.root)
            print()

Solution (Python):
class BinarySearchTree:
    def __init__(self):
        self.root = None
    def show_keys(self):
        in_order_from(self.root)
        print('')
        pre_order_from(self.root)
        print('')
    def insert(self, key):
        node = Node(key)
        insert(self, node)
    def find(self, key):
        if find_from(self.root, key):
            print('yes')
        else:
            print('no')
    def delete_key(self, key):
        node = find_from(self.root, key)
        delete_node(self, node)

class Node:
    def __init__(self, key):
        self.key = key
        self.parent = None
        self.left = None
        self.right = None

def insert(T, z):
    y = None
    x = T.root
    while x != None:
        y = x
        if z.key < x.key:
            x = x.left
        else:
            x = x.right
    z.parent = y
    if y == None:
        T.root = z
    elif z.key < y.key:
        y.left = z
    else:
        y.right = z

def delete_node(T, node):
    if node.left and node.right:
        x = node.right
        while x.left:
            x = x.left
        node.key = x.key
        delete_node(T, x)
    elif node.left or node.right:
        child = node.left or node.right
        if node is T.root:
            T.root = child
            child.parent = None
        else:
            if node.parent.left is node:
                node.parent.left = child
                child.parent = node.parent
            else:
                node.parent.right = child
                child.parent = node.parent
    else:
        if node.parent.left is node:
            node.parent.left = None
        else:
            node.parent.right = None

def in_order_from(node):
    if node:
        in_order_from(node.left)
        print(' {0}'.format(node.key), end = '')
        in_order_from(node.right)

def pre_order_from(node):
    if node:
        print(' {0}'.format(node.key), end = '')
        pre_order_from(node.left)
        pre_order_from(node.right)

def find_from(node, k):
    while node:
        if node.key == k:
            return node
        if k < node.key:
            node = node.left
        else:
            node = node.right


import sys

t = BinarySearchTree()

m = sys.stdin.readline()

for i in sys.stdin.readlines():
    if i[0] == 'i':
        t.insert(int(i[7:]))
    elif i[0] == 'f':
        t.find(int(i[5:]))
    elif i[0] == 'd':
        t.delete_key(int(i[7:]))
    else:
        t.show_keys()

Solution (Python):
class node:
    def __init__(self,key=None):
        self.left=None
        self.right=None
        self.parent=None
        self.key=key

def insert(T,z):
    x=T
    y=None
    while isinstance(x,node):
        y=x
        if z.key<x.key:
            x=x.left
        else:
            x=x.right
    z.parent=y
    if y is None:
        T=z
    elif z.key<y.key:
        y.left=z
    else:
        y.right=z
    return T

def find(T,z):
    if T is None:
        return False
    else:
        y=None
        x=T
        while 1:
            y=x
            if x is None:
                return False
            elif z.key==x.key:
                return True
            elif z.key<x.key:
                x=x.left
            else:
                x=x.right
                
def delete(T,z,i):
    if i==0:
        x=T
        y=None
        while 1:    
            y=x
            if x is None:
                return 
            elif z.key==x.key:
                break
            elif z.key<x.key:
                x=x.left
            else:
                x=x.right
            z.parent=y
        z=x     
    if z.left is None and z.right is None:
        if z is z.parent.right:
            z.parent.right=None
        else:
            z.parent.left=None
    elif z.left is None:
        if z is z.parent.left:
            z.parent.left=z.right
            z.right.parent=z.parent
        else:
            z.parent.right=z.right
            z.right.parent=z.parent
    elif z.right is None:
        if z is z.parent.left:
            z.parent.left=z.left
            z.left.parent=z.parent
        else:
            z.parent.right=z.left
            z.left.parent=z.parent
    else:
        y=del_inorder(z.right)
        z.key=y.key
        delete(T,y,1)
           
def preorder(u):
    if u is None:
        return
    pripre.append(str(u.key))
    preorder(u.left)
    preorder(u.right)

def inorder(u):
    if u is None:
        return
    inorder(u.left)
    priin.append(str(u.key))
    inorder(u.right)
    
def del_inorder(u):
    if u is None:
        return
    del_inorder(u.left)
    Min.append(u)
    del_inorder(u.right)
    return Min[0]

m=input()
root=None
for i in xrange(m):
    cmd=map(str,raw_input().split())
    if cmd[0]=="print":
        pripre=[]
        priin=[]
        preorder(root)
        inorder(root)
        print(' '+' '.join(priin))
        print(' '+' '.join(pripre))
    elif cmd[0]=="find":
        key=int(cmd[1])
        z=node(key)
        if find(root,z):
            print('yes')
        else:
            print('no')
    elif cmd[0]=='delete':
        Min=[]
        key=int(cmd[1])
        z=node(key)
        delete(root,z,0)
    else:
        key=int(cmd[1])
        z=node(key)
        root=insert(root,z)

Solution (Python):
class Node():
	def __init__(self, key):
		self.parent = None
		self.left = None
		self.right = None
		self.key = key
 
class Tree():
	def __init__(self):
		self.root = None
	def insert_node(self, key):
		z = Node(key)
		y = None
		x = self.root
		while x:
			y = x
			if z.key < x.key:
				x = x.left
			else:
				x = x.right
		z.parent = y
		if y == None:
			self.root = z;
		elif z.key < y.key:
			y.left = z
		else:
			y.right = z
	def delete_node(self, key):
		node = self.find_node(key)
		if node.left and node.right:
			right_min = node.right
			while right_min.left:
				right_min = right_min.left
			node.key = right_min.key
			node = right_min
		if node.left or node.right:
			child = node.left if node.left else node.right
			if node.parent.left == node:
				node.parent.left = child
				child.parent = node.parent
			else:
				node.parent.right = child
				child.parent = node.parent
		else:
			if node.parent.left == node:
				node.parent.left = None
			else:
				node.parent.right = None

	def pre_order(self, node):
		print(" {}".format(node.key), end = "")
		if node.left:
			self.pre_order(node.left)
		if node.right:
			self.pre_order(node.right)
	def in_order(self, node):
		if node.left:
			self.in_order(node.left)
		print(" {}".format(node.key), end = "")
		if node.right:
			self.in_order(node.right)
	def print_node(self):
		self.in_order(self.root)
		print("")
		self.pre_order(self.root)
		print("")
	def find_node(self, key):
		node = self.root;
		while node:
			if node.key == key:
				return node
			elif node.key > key:
				node = node.left
			else:
				node = node.right
		return None

tree = Tree()
n = int(input())
for i in range(n):
	c = input().split()
	if c[0] == "insert":
		tree.insert_node(int(c[1]))
	elif c[0] == "find":
		print("yes" if tree.find_node(int(c[1])) else "no")
	elif c[0] == "delete":
		tree.delete_node(int(c[1]))
	else:
		tree.print_node()

Solution (Python):
import sys
import time

class Node:
    def __init__(self, key):
        self.key = key
        self.parent = None
        self.left = None
        self.right = None

def insert(z):
    global root
    y = None
    x = root
    while x is not None:
        y = x
        if z.key < x.key:
            x = x.left
        else:
            x = x.right
    z.parent = y
    if y is None:
        root = z
    elif z.key < y.key:
        y.left = z
    else:
        y.right = z

def find(node, key):
    if node is None:
        return False
    elif node.key == key:
        return True
    elif node.key > key:
        return find(node.left, key)
    else:
        return find(node.right, key)

def delete(node, key):
    if node is not None:
        if node.key == key:
            reconstTree(node)
        elif node.key > key:
            delete(node.left, key)
        else:
            delete(node.right, key)

def reconstTree(node):
    if node.left is None and node.right is None:
        
        
        if node.parent.left == node:
            node.parent.left = None
        else:
            node.parent.right = None
    elif node.left is not None and node.right is not None:
        
        
        sib = node.right
        while sib.left is not None:
            sib = sib.left
        node.key = sib.key
        reconstTree(sib)
    elif node.left is not None:
        
        
        if node.parent.left == node:
            node.parent.left = node.left
        else:
            node.parent.right = node.left
        node.left.parent = node.parent
    else:
        
        
        if node.parent.left == node:
            node.parent.left = node.right
        else:
            node.parent.right = node.right
        node.right.parent = node.parent

def inorderTreeWalk(node):
    global In
    if node:
        inorderTreeWalk(node.left)
        In.append(str(node.key))
        inorderTreeWalk(node.right)

def preorderTreeWalk(node):
    global Pre
    if node:
        Pre.append(str(node.key))
        preorderTreeWalk(node.left)
        preorderTreeWalk(node.right)

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    del lines[0]

    root = None
    for line in lines:
        if line[0] == "p":
            In = []
            Pre = []
            inorderTreeWalk(root)
            print " " + " ".join(map(str, In))
            preorderTreeWalk(root)
            print " " + " ".join(map(str, Pre))
        else:
            com = line.split()
            if com[0][0] == "i":
                insert(Node(int(com[1])))
            elif com[0][0] == "f":
                if find(root, int(com[1])):
                    print "yes"
                else:
                    print "no"
            else:
                delete(root, int(com[1]))

Solution (Python):
import sys

class Node:
    def __init__(self, key):
        self.key = key
        self.parent = None
        self.left = None
        self.right = None

def insert(z):
    global root
    y = None
    x = root
    while x is not None:
        y = x
        if z.key < x.key:
            x = x.left
        else:
            x = x.right
    z.parent = y
    if y is None:
        root = z
    elif z.key < y.key:
        y.left = z
    else:
        y.right = z

def find(node, key):
    if node is None:
        return False
    elif node.key == key:
        return True
    elif node.key > key:
        return find(node.left, key)
    else:
        return find(node.right, key)

def delete(node, key):
    if node is not None:
        if node.key == key:
            reconstTree(node)
        elif node.key > key:
            delete(node.left, key)
        else:
            delete(node.right, key)

def reconstTree(node):
    if node.left is not None and node.right is not None:
        sib = node.right
        while sib.left is not None:
            sib = sib.left
        node.key = sib.key
        reconstTree(sib)
    else:
        parent = node.parent
        if node.left is not None:
            child = node.left
        elif node.right is not None:
            child = node.right
        else:
            child = None

        if parent.left == node:
            parent.left = child
        else:
            parent.right = child

        if child is not None:
            child.parent = parent

def inorderTreeWalk(node):
    global In
    if node:
        inorderTreeWalk(node.left)
        In.append(str(node.key))
        inorderTreeWalk(node.right)

def preorderTreeWalk(node):
    global Pre
    if node:
        Pre.append(str(node.key))
        preorderTreeWalk(node.left)
        preorderTreeWalk(node.right)

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    del lines[0]

    root = None
    for line in lines:
        if line[0] == "p":
            In = []
            Pre = []
            inorderTreeWalk(root)
            print " " + " ".join(map(str, In))
            preorderTreeWalk(root)
            print " " + " ".join(map(str, Pre))
        else:
            com = line.split()
            if com[0][0] == "i":
                insert(Node(int(com[1])))
            elif com[0][0] == "f":
                if find(root, int(com[1])):
                    print "yes"
                else:
                    print "no"
            else:
                delete(root, int(com[1]))

Solution (Python):
import sys
import os

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        
    def insert_node(self, node):
        if node.value <= self.value:
            if self.left is None:
                self.left = node
            else:
                self.left.insert_node(node)
        else:
            if self.right is None:
                self.right = node
            else:
                self.right.insert_node(node)

    def find_node_by_value(self, value):
        if self.value == value:
            return self
        elif value < self.value:
            if self.left is None:
                return None
            else:
                return self.left.find_node_by_value(value)
        elif value > self.value:
            if self.right is None:
                return None
            else:
                return self.right.find_node_by_value(value)
        else:
            assert(False)   

    def next_node_in_inorder(self):
        if self.right is not None:
            return self.right.smallest_offspring(self)
        else:
            return None

    def smallest_offspring(self, parent):
        if self.left is not None:
            return self.left.smallest_offspring(self)
        else:
            return (self, parent)

    def get_parent_of(self, value, parent_cand=None, is_left_child=None):
        if self.value == value:
            return parent_cand, is_left_child
        else:
            if value < self.value and self.left is not None:
                return self.left.get_parent_of(value, self, True)
            elif value > self.value and self.right is not None:
                return self.right.get_parent_of(value, self, False)
            else:
                assert(False)

    def delete_child(self, node):
        if self.left == node:
            self.left = None
        elif self.right == node:
            self.right = None
        else:
            assert(False)
            
    def delete_node(self, parent, value):
        
        if value < self.value and self.left is not None:
            self.left.delete_node(self, value)
        elif self.value < value and self.right is not None:
            self.right.delete_node(self, value)
        
        elif self.left is None and self.right is None:
            
            parent.delete_child(self)
        elif self.left is not None and self.right is not None:
            n, p = self.next_node_in_inorder()
            self.value = n.value
            n.delete_node(p, n.value)
        elif self.left is not None:
            self.value = self.left.value
            self.right = self.left.right
            self.left = self.left.left
        elif self.right is not None:
            self.value = self.right.value
            self.left = self.right.left
            self.right = self.right.right
    















                
    def print_node_by_preorder(self):
        print('', self.value, end='')
        if self.left is not None:
            self.left.print_node_by_preorder()
        if self.right is not None:
            self.right.print_node_by_preorder()


    def print_node_by_inorder(self):
        if self.left is not None:
            self.left.print_node_by_inorder()
        print('', self.value, end='')
        if self.right is not None:
            self.right.print_node_by_inorder()

class BST:
    def __init__(self):
        self.root = None

    def cmd_insert(self, k):
        if self.root is None:
            self.root = Node(k)
        else:
            self.root.insert_node(Node(k))

    def cmd_find(self, k):
        if self.root is None:
            return False
        else:
            return (self.root.find_node_by_value(k) is not None)

    def cmd_delete(self, k):
        if self.root is None:
            pass
        else:
            self.root.delete_node(parent=self, value=k)

    def delete_child(self, node):
        assert(self.root == node)
        self.root = None

    def cmd_print(self):
        if self.root is not None:
            self.root.print_node_by_inorder()
            print()
            self.root.print_node_by_preorder()
            print()


if __name__ == '__main__':
    bst = BST()

    lines = []
    for line in sys.stdin:
        lines.append(line.rstrip())
    num_cmds = int(lines[0])
    for line in lines[1:1+num_cmds]:
        line_split = line.split(' ')
        cmd = line_split[0]

        try:
            val = int(line_split[1])
        except:
            pass
        if cmd == 'insert':
            bst.cmd_insert(val)
        elif cmd == 'find':
            if bst.cmd_find(val):
                print('yes')
            else:
                print('no')
        elif cmd == 'print':
            bst.cmd_print()
        elif cmd == 'delete':
            bst.cmd_delete(val)
        else:
            assert(False)

Solution (Python):


class Node:
    def __init__(self, key):
        self.key = key
        self.parent = None
        self.left = None
        self.right = None
class Tree:
    def __init__(self):
        self.root = None

    def insert(self, node):
        y = None 
        x = self.root
        while x is not None:
            y = x
            if node.key < x.key:
                x = x.left
            else:
                x = x.right
    
        if y is None:
            self.root = node
        elif node.key < y.key:
            y.left = node
            node.parent = y
        else:
            y.right = node
            node.parent = y

    def find(self, node, key):
        if node is None:
            return None

        if key == node.key:
            return node
        elif key < node.key:
            return self.find(node.left, key)
        else:
            return self.find(node.right, key)

    def delete(self, key):
        del_node = self.find(self.root, key)
        if del_node.right and del_node.left:
            
            right_min = del_node.right
            while right_min.left:
                right_min = right_min.left
            tmp = right_min.key
            self.delete(right_min.key)
            del_node.key = tmp
        elif del_node.right or del_node.left:
            
            child = del_node.right if del_node.right else del_node.left
            if del_node.parent.right == del_node:
                del_node.parent.right = child
                child.parent = del_node.parent
            else:
                del_node.parent.left = child
                child.parent = del_node.parent
        else:
            
            if del_node.parent.right == del_node:
                del_node.parent.right = None
            else:
                del_node.parent.left = None


def inorder(node):
    if node is None:
        return
    inorder(node.left)
    print(" {}".format(node.key), end = "")
    inorder(node.right)

def preorder(node):
    if node is None:
        return
    print(" {}".format(node.key), end = "")
    preorder(node.left)
    preorder(node.right)

def execute(tree, cmd):
    if cmd[0] == 'insert':
        t.insert(Node(int(cmd[1])))
    elif cmd[0] == 'find':
        if tree.find(tree.root, int(cmd[1])):
            print('yes')
        else:
            print('no')
    elif cmd[0] == 'delete':
        tree.delete(int(cmd[1]))
    else:
        inorder(t.root)
        print()
        preorder(t.root)
        print()

m = int(input())
t = Tree()
for i in range(m):
    execute(t, input().split())