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 BinaryTree:
    def __init__(self, left, right, parent):
        self.left = left
        self.right = right
        self.parent = parent
        self.key = None
        self.root = False
        

def insert(T, z):
    global root
    
    y = -1
    try:
        x = root
    except:
        x = -1
        root = z
        T[z].root = True
    
    while x != -1:
        y = x
        if T[z].key < T[x].key:
            x = T[x].left
        else:
            x = T[x].right
    T[z].parent = y
    
    if y == -1:
        pass
    
    elif T[z].key < T[y].key:
        T[y].left = z
        
    else:
        T[y].right = z

def find(T, z, s):
    if s == -1:
        return [False, None]
        
    elif T[s].key == z:
        return [True, s]
        
    elif T[s].key < z:
        return find(T, z, T[s].right)
        
    else:
        return find(T, z, T[s].left)

def delete(T, z):
    global root
    z_has_left = T[z].left != -1
    z_has_right = T[z].right != -1
    
    
    if (not z_has_left) or (not z_has_right):
        y = z
    else:
        y = getsucsessor(T, z)


    if T[y].left != -1:
        x = T[y].left
    else:
        x = T[y].right
    
    if x != -1:
        T[x].parent = T[y].parent
    
    if T[y].root:
        T[x].root = True
        T[y].root = False
        root = x
    
    elif T[T[y].parent].left == y:
        T[T[y].parent].left = x
    else:
        T[T[y].parent].right = x
    
    T[z].key = T[y].key
    T[y] = BinaryTree(-1, -1, -1)

def getsucsessor(T, x):
    if T[x].right != -1:
        
        return getMinimum(T, T[x].right)
        
    else:
        y = T[x].parent
        while (y != -1) and (T[y].right == x):
            x = y
            y = T[y].parent
        return y

def getMinimum(T, x):
    while T[x].left != -1:
        x = T[x].left
    return x
        
    
def preParse(u):
    if u == -1:
        return 0
    print(" " + str(T[u].key), end="")
    preParse(T[u].left)
    preParse(T[u].right)

def inParse(u):
    if u == -1:
        return 0
    inParse(T[u].left)
    print(" " + str(T[u].key), end="")
    inParse(T[u].right)

m = int(input().rstrip())

z = 0
T = []
for _ in range(m):
    T.append(BinaryTree(-1, -1, -1))

for _ in range(m):
    command = input().rstrip()
    if command =="print":
        inParse(root)
        print()
        preParse(root)
        print()
    else:
        command, key = command.split(" ")
        key = int(key)
    
    
    if command == "insert":
        T[z].key = key
        insert(T, z)
        z += 1
        
    elif command == "find":
        if find(T, key, root)[0]:
            print("yes")
        else:
            print("no")
    
    elif command == "delete":
        x = find(T, key, root)[1]
        
        delete(T, x)

Solution (Python):
n=int(input())
tree={}
root=None

def insert(tree,number):
    parent=None
    children=root
    while children!=None:
        parent=children
        if number>children:
            children=tree[parent][1]
        else:
            children=tree[parent][0]
    tree[number][2]=parent
    if number>parent:
        tree[parent][1]=number
    else:
        tree[parent][0]=number

def preorder(tree,i):
    if i==None:
        return
    print(" {}".format(i),end="")
    preorder(tree,tree[i][0])
    preorder(tree,tree[i][1])

def inorder(tree,i):
    if i==None:
        return
    inorder(tree,tree[i][0])
    print(" {}".format(i),end="")
    inorder(tree,tree[i][1])

def find(x,number):
    while x!=None and number!=x:
        if x>number:
            x=tree[x][0]
        else:
            x=tree[x][1]
    return x

def find_parent(x,number):
    y=0
    t=-1
    while x!=None and number!=x:
        y=x
        if x>number:
            x=tree[x][0]
            t=0
        else:
            x=tree[x][1]
            t=1
    return y,t

def get_minimum(tree,number):
    while tree[number][0]!=None:
        number=tree[number][0]
    return number    

def delete(tree,number):
    if tree[number][0]==None and tree[number][1]==None:
        y,t=find_parent(root,number)
        tree[y][t]=None
    elif tree[number][0]==None or tree[number][1]==None:
        if tree[number][0]==None:
            next_number=tree[number][1]
        else:
            next_number=tree[number][0]
        y,t=find_parent(root,number)
        tree[y][t]=next_number
    elif tree[number][0]!=None and tree[number][1]!=None:
        next_number=get_minimum(tree,tree[number][1])
        y,t=find_parent(root,number)
        next_y,next_t=find_parent(root,next_number)
        left,right=tree[number][0],tree[number][1]
        if tree[number][1]==next_number:
            right=None
        tree[y][t]=next_number
        tree[next_y][next_t]=None
        tree[next_number]=[left,right]


for i in range(n):
    tmp=list(input().split())
    if tmp[0]=="print":
        inorder(tree,root)
        print()
        preorder(tree,root)
        print()
    else:
        number=int(tmp[1])
        if tmp[0]=="insert":
            if root==None:
                root=number
                tree[number]=[None,None,None]
            else:
                tree[number]=[None,None,None]
                insert(tree,number)
            
        elif tmp[0]=="find":
            if find(root,number) is not None:
                print("yes")
            else:
                print("no")
        
        else:
            delete(tree,number)

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

class Tree:
    root = None
    preorder_list = []
    inorder_list = []
    def __init__(self):
        pass
    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
        node.parent = y

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

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

    def delete(self, node):
        y = None
        x = self.root

        while x is not None:
            y = x
            if node.key < x.key:
                x = x.left
            elif node.key > x.key:
                x = x.right
            else:
                break
        if y.left is None and y.right is None:
            if y.parent.left == y:
                y.parent.left = None
            if y.parent.right == y:
                y.parent.right = None
        elif y.left is None or y.right is None:
            tmp = y.left or y.right
            tmp.parent = y.parent
            if tmp.parent.left == y:
                tmp.parent.left = tmp
            if tmp.parent.right == y:
                tmp.parent.right = tmp
        else:
            tmp = self.successor(y)
            y.key = tmp.key
            if tmp.parent.left == tmp:
                tmp.parent.left = None
            if tmp.parent.right == tmp:
                tmp.parent.right = None

            pass

    def successor(self, node):
        node = node.right
        while node.left:
            node = node.left
        return node

    def display(self):
        
        self.inorder(self.root)
        self.preorder(self.root)
        print(' '+' '.join(map(str, self.inorder_list)))
        print(' '+' '.join(map(str, self.preorder_list)))
        pass

    def preorder(self, node):
        if node == None:
            return
        self.preorder_list.append(node.key)
        if node.left is not None:
            self.preorder(node.left)
        if node.right is not None:
            self.preorder(node.right)

    def inorder(self, node, depth=0):
        if node == None:
            return
        if node.left is not None:
            self.inorder(node.left)
        self.inorder_list.append(node.key)
        if node.right is not None:
            self.inorder(node.right)

n = int(input())
command_list = [list(input().split()) for _ in range(n)]

tree = Tree()
for command in command_list:
    if command[0] == 'insert':
        node = Node(int(command[1]))
        tree.insert(node)
        
    if command[0] == 'print':
        tree.display()
        tree.preorder_list = []
        tree.inorder_list = []
    if command[0] == 'find':
        if tree.find(Node(int(command[1]))) is None:
            print('no')
        else:
            print('yes')
    if command[0] == 'delete':
        result = tree.delete(Node(int(command[1])))

Solution (Python):
class Node:
    def __init__(self, key):
        self.key = key
        self.parent = None
        self.left = self.right = None
    def nextNode(self):
        if not self.right:
            return None
        x = self.right
        while x.left:
            x = x.left
        return x
    def preorder(self):
        L = [self.key]
        if self.left: L += self.left.preorder()
        if self.right: L += self.right.preorder()
        return L
    def inorder(self):
        L = []
        if self.left: L += self.left.inorder()
        L.append(self.key)
        if self.right: L += self.right.inorder()
        return L

def insert(t, z):
    y = None
    x = t
    while x:
        y = x 
        x = x.left if z.key < x.key else x.right
    z.parent = y
    if not y: 
        return z
    if z.key < y.key:
        y.left = z 
    else:
        y.right = z 
    return t

def find(t, k):
    x = t
    while x:
        if x.key == k:
            return x
        x = x.left if k < x.key else x.right
    return None

def delete(t, k):
    node = find(t, k)
    delNode(node)

def delNode(node):
    if not node: return
    if not node.left and not node.right: 
        if node == node.parent.left:
            node.parent.left = None
        if node == node.parent.right:
            node.parent.right = None
    elif not node.right: 
        if node == node.parent.left:
            node.parent.left = node.left
        if node == node.parent.right:
            node.parent.right = node.left
        node.left.parent = node.parent
    elif not node.left: 
        if node == node.parent.left:
            node.parent.left = node.right
        if node == node.parent.right:
            node.parent.right = node.right
        node.right.parent = node.parent
    else: 
        next = node.nextNode()
        node.key = next.key
        delNode(next)

t = None
m = int(input())
for _ in range(m):
    cmd = list(input().split())
    if cmd[0] == 'insert':
        t = insert(t, Node(int(cmd[1])))
    if cmd[0] == 'find':
        print('yes' if find(t, int(cmd[1])) else 'no')
    if cmd[0] == 'delete':
        delete(t, int(cmd[1]))
    if cmd[0] == 'print':
        print('', *t.inorder())
        print('', *t.preorder())

Solution (Python):
import sys
sys.setrecursionlimit(2**20)  


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

ROOT = None

def pre_parse(u, pre_ls):
    if u == None:
        return
    pre_ls.append(u.key)
    pre_parse(u.left, pre_ls) 
    pre_parse(u.right, pre_ls)


def in_parse(u, in_ls):
    if u == None:
        return
    in_parse(u.left, in_ls)
    in_ls.append(u.key)
    in_parse(u.right, in_ls)


def insert(value):
    global ROOT
    y = None
    x = ROOT
    z = Node(value)  
    while x != None:
        y = x  
        if z.key < x.key:
            x = x.left
        else:
            x = x.right
            
    z.parent = y

    if y == None:
        ROOT = z
    else:
        if z.key < y.key:
            y.left = z
        else:
            y.right = z


def find(u, value):
    while u != None and u.key != value:
        if value < u.key:
            u = u.left
        else:
            u = u.right
    return u


def deleteNode(z):
    
    if (z.left == None or z.right == None):
        y = z
    else:
        y = getSucessor(z)

    if y.left is not None:
        x = y.left
    else:
        x = y.right

    if x is not None:
        x.parent = y.parent

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

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

def getSucessor(x):
    if x.right is not None:
        return getMinimum(x.right)

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


def getMinimum(x):
    while x.left != None:
        x = x.left
    return x
    
    
def print_result():
    pre_ls, in_ls = [], []
    in_parse(ROOT, in_ls)
    pre_parse(ROOT, pre_ls)
    print('', *in_ls)
    print('', *pre_ls)

n = int(input())

for i in range(n):
    tmp = input()
    if tmp[0] == "p":
        print_result()
    elif tmp[0] == "f":
        if find(ROOT, int(tmp[5:])):
            print("yes")
        else:
            print("no")
    elif tmp[0] == "i":
        insert(int(tmp[7:]))
    else:
        deleteNode(find(ROOT, int(tmp[7:])))

Solution (Python):
import sys






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


def insert(key):
    global root
    x = root 
    y = None  
    while x:
        y = x 
        if key < x.key:
            x = x.left 
        else:
            x = x.right 
    
    if root is None:
        root = Node(key)
    elif key < y.key: 
        y.left = Node(key)
        y.left.parent = y
    else: 
        y.right = Node(key) 
        y.right.parent = y
        
def find(key):
    global root
    x = root
    while x:
        if key==x.key:
            print('yes')
            return
        elif key < x.key:
            x = x.left
        else:
            x = x.right
    print('no')
    
    
def minimum(x):
    while x.left:
        x = x.left
    return x
    
    
def successor(x):
    if x.right:
        return minimum(x.right)
    y = x.parent
    while (y) and (x==y.right):
        x = y
        y = y.parent
    return y
    
    
    
def delete(key):
    global root
    
    
    z = None
    x = root
    while x:
        if key==x.key:
            z = x
            break
        elif key < x.key:
            x = x.left
        else:
            x = x.right
    if z is None:
        return
    
    
    if (z.left==None) or (z.right==None):
        y = z
    else:
        y = successor(z)
        
    if y.left:
        x = y.left
    else:
        x = y.right
        
    if x:
        x.parent = y.parent
    
    if y.parent is None:
        root = x
    elif y==y.parent.left:
        y.parent.left = x
    else:
        y.parent.right = x
        
    if y!=z:
        z.key = y.key
    

def inorder(inorder_list, node):
    if node.left is not None:
        inorder(inorder_list, node.left)
    inorder_list.append(str(node.key))
    if node.right is not None:
        inorder(inorder_list, node.right)
    return inorder_list
        
def preorder(preorder_list, node):
    preorder_list.append(str(node.key))
    if node.left is not None:
        preorder(preorder_list, node.left)
    if node.right is not None:
        preorder(preorder_list, node.right)
    return preorder_list
        
root = None

input()
for o in sys.stdin:
    if o[0]=='i':
        insert(int(o[7:]))
    elif o[0]=='f':
        find(int(o[5:]))
    elif o[0]=='d':
        delete(int(o[7:]))
    else:
        x = root
        inorder_list = inorder([], x)
        print(' '+' '.join(inorder_list))
        preorder_list = preorder([], x)
        print(' '+' '.join(preorder_list))

Solution (Python):
import sys, collections
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**10
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

class Node():
    key = None
    p = None
    left = None
    right = None

    def __init__(self, key):
        self.key = key

class BinarySearchTree():
    root = None

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

        if y is None:
            self.root = z
        elif z.key < y.key:
            y.left = z
        else:
            y.right = z

    def find(self, k):
        x = self.root
        while x is not None:
            if x.key==k:
                return x
            elif x.key>k:
                x = x.left
            else:
                x = x.right
        return None

    def next_node(self, z):
        if z.right is None:
            x = z
            y = z.p
            while y is not None and y.left!=x:
                x = y
                y = y.p
            
            return y
        else:
            x = z.right
            while x is not None:
                y = x
                x = x.left
            return y

    def delete(self, k):
        z = self.find(k)
        if z.left is None and z.right is None:
            if z.p.key > z.key:
                z.p.left = None
            else:
                z.p.right = None
        elif z.left is not None and z.right is not None:
            y = self.next_node(z)
            tmp = y.key
            self.delete(y.key)
            z.key = tmp
        else:
            if z.right is None:
                z_child = z.left
            else:
                z_child = z.right
            z_child.p = z.p
            if z.p.key > z.key:
                z.p.left = z_child
            else:
                z.p.right = z_child
            
    def print_nodes(self):
        inorder = []
        preorder = []

        def dfs(v):
            v_key = v.key
            preorder.append(v_key)
            if v.left is not None:
                dfs(v.left)
            inorder.append(v_key)
            if v.right is not None:
                dfs(v.right)

        dfs(self.root)

        print('', *inorder)
        print('', *preorder)

def resolve():
    m = I()
    T = BinarySearchTree()
    for _ in range(m):
        q = LSS()
        if q[0]=='insert':
            k = int(q[1])
            z = Node(k)
            T.insert(z)
        elif q[0]=='find':
            k = int(q[1])
            if T.find(k):
                print('yes')
            else:
                print('no')
        elif q[0]=='delete':
            k = int(q[1])
            T.delete(k)
        else:
            T.print_nodes()
    
    
    
    
    
    

if __name__ == '__main__':
    resolve()

Solution (Python):
import sys
sys.setrecursionlimit(2**20)  


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


def pre_parse(T: dict, u: int, pre_ls: list):
    
    if u == None:
        return
    pre_ls.append(u)
    pre_parse(T, T[u].left, pre_ls)  
    pre_parse(T, T[u].right, pre_ls)


def in_parse(T, u, in_ls):
    if u == None:
        return
    
    in_parse(T, T[u].left, in_ls)
    in_ls.append(u)
    in_parse(T, T[u].right, in_ls)


def insert(T, ROOT, z):
    '''
    zは接点番号(そしてその接点番号が内容でもある)
    この接点番号を二分探索木の条件に従うように挿入する。
    '''
    
    if ROOT == z:
        T[z] = Node()
    
    else:
        T[z] = Node()  
        x = ROOT
        while x is not None:  
            next_parent = x  
            if z < x:  
                x = T[x].left
            else:
                x = T[x].right
        T[z].parent = next_parent
        
        if z < next_parent:
            T[next_parent].left = z
        else:
            T[next_parent].right = z


def find(T, ROOT, k):
    '''
    Tからkを見つけ出す。見つからなかったらNoneを返す
    ひたすらkの大きさによって左右のパスをたどっていくだけ
    (いま辞書でノードを管理しているので、`k in T.keys()`で済むことではあるんだけど(オーダーは大きくなる)))
    '''
    x = ROOT  
    while x is not None and x != k:
        if k < x:
            x = T[x].left
        else:
            x = T[x].right
    return x


def delete_node(T, z):
    
    parent = T[z].parent
    if (T[z].left is None) and (T[z].right is None):
        
        if T[parent].left == z:
            T[parent].left = None
        elif T[parent].right == z:
            T[parent].right = None
        else:
            raise ValueError('something wrong in case 1')
        del T[z]
    
    elif T[z].right is None:
        
        
        z_is_left = True if T[parent].left == z else False
        child = T[z].left
        if z_is_left:
            T[parent].left = child
        else:
            T[parent].right = child
        T[child].parent = parent
        del T[z]
    elif T[z].left is None:
        
        z_is_left = True if T[parent].left == z else False
        child = T[z].right
        if z_is_left:
            T[parent].left = child
        else:
            T[parent].right = child
        T[child].parent = parent
        del T[z]
    
    elif (T[z].left is not None) and (T[z].right is not None):
        
        left, right = T[z].left, T[z].right
        node_next_more = get_min_in_descendants(
            T, T[z].right)  
        next_more_right = T[node_next_more].right
        next_more_parent = T[node_next_more].parent
        
        if parent is None:
            if node_next_more == right:
                
                T[right].parent = None
                T[right].left = left
                ROOT = right
                del T[z]
                return
            else:
                
                
                T[node_next_more].left = left
                T[node_next_more].right = right
                T[node_next_more].parent = None
                T[left].parent = node_next_more  
                T[right].parent = node_next_more  
                
                if next_more_right is not None:
                    T[next_more_right].parent = next_more_parent
                ROOT = node_next_more
                del T[z]
                return
        else:  
            
            z_is_left = True if T[parent].left == z else False
            if node_next_more == right:
                if z_is_left:
                    T[parent].left = right
                else:
                    T[parent].right = right
                T[right].parent = parent
                T[right].left = left
                del T[z]
                return
            else:  
                
                if z_is_left:
                    T[parent].left = node_next_more
                else:
                    T[parent].right = node_next_more
                
                T[node_next_more].left = T[z].left
                T[node_next_more].right = T[z].right
                T[node_next_more].parent = parent
                T[left].parent = node_next_more  
                T[right].parent = node_next_more  
                
                T[next_more_parent].left = next_more_right
                if next_more_right is not None:
                    T[next_more_right].parent = next_more_parent

                del T[z]
                return


def get_min_in_descendants(T, z):
    x = z
    while T[x].left is not None:
        x = T[x].left
    return x


def print_result(T):
    pre_ls, in_ls = [], []
    in_parse(T, ROOT, in_ls)
    pre_parse(T, ROOT, pre_ls)
    print('', *in_ls)
    print('', *pre_ls)


    
N = int(input())
T = {}
for i in range(N):
    tmp = input()
    if tmp.startswith('print'):  
        print_result(T)
    elif tmp.startswith('insert'):
        z = int(tmp.split()[1])
        if i == 0:
            ROOT = z
        insert(T, ROOT, z)
    elif tmp.startswith('find'):
        z = int(tmp.split()[1])
        if find(T, ROOT, z) is None:
            print('no')
        else:
            print('yes')
    elif tmp.startswith('delete'):
        z = int(tmp.split()[1])
        delete_node(T, z)

Solution (Python):
from collections import deque
import sys
readline = sys.stdin.readline
write = sys.stdout.write

class Node:
    __slots__ = ['key', 'left', 'right']
    def __init__(self, key):
        self.key = key
        self.left = self.right = None


root = None

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

    if y is None: 
        root = Node(key)
    elif key < y.key:
        y.left = Node(key) 
    else:
        y.right = Node(key) 

def delete(target):
    def remove_node(p,c,a):
        if p.left == c: p.left = a
        else: p.right = a
    p,c = None,root
    while c.key != target: p,c = c,c.left if target < c.key else c.right
    if c.left is None:
        remove_node(p, c, c.right)
    elif c.right is None:
        remove_node(p, c, c.left)
    elif c.right.left is None:
        c.right.left = c.left
        remove_node(p, c, c.right)
    else:
        g = c.right
        while g.left.left: g = g.left
        c.key = g.left.key
        g.left = g.left.right







def find(target):
    result = root
    while result and target != result.key:
        result = result.left if target < result.key else result.right
    return result is None 

def inorder(node):
    return   inorder(node.left) + " "+ str(node.key) + inorder(node.right) if node else ''
def preorder(node):
    return   " " + str(node.key) + preorder(node.left) + preorder(node.right) if node else ''
input()
for e in sys.stdin:
    if e[0] == "i":
        insert(int(e[7:]))
    elif e[0] == 'f':
        if find(int(e[5:])):
            print("no")
        else:
            print("yes")
        

    elif e[0] == 'd':
        delete(int(e[7:]))

    else:
        print(inorder(root))
        print(preorder(root))