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):
def insert(tree,node):
    parent=None
    child=root
    while child is not None:
        parent=child
        if node<child:child=tree[parent][0]
        else:child=tree[parent][1]
    if node<parent:tree[parent][0]=node
    else:tree[parent][1]=node


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


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


def find(x,key):
    while x is not None and key!=x:
        if key<x:x=tree[x][0]
        else:x=tree[x][1]
    return x


def parent_search(tree,node):
    parent=None
    child=root
    while child is not None and child!=node:
        parent=child
        if node<child:child=tree[parent][0]
        else:child=tree[parent][1]
    return parent


def getMinimum(node):
    while tree[node][0] is not None:
        node=tree[node][0]
    return node


def getSuccessor(node):
    if tree[node][1] is not None:
        return getMinimum(tree[node][1])
    target=parent_search(tree,node)
    while target is not None and node==tree[target][1]:
        node=target
        target=parent_search(tree,target)
    return target


def delete(tree,node):
    if tree[node][0] is None or tree[node][1] is None:target=node
    else:target=getSuccessor(node)

    if tree[target][0] is not None:child=tree[target][0]
    else:child=tree[target][1]

    child_parent=parent_search(tree,target)
    if target==tree[child_parent][0]:tree[child_parent][0]=child
    else:tree[child_parent][1]=child
    if target==node:
        del tree[node]
        return

    node_parent=parent_search(tree,node)
    if node==tree[node_parent][0]:tree[node_parent][0]=target
    else:tree[node_parent][1]=target
    tree[target]=tree[node]
    del tree[node]


n=int(input())
tree,root={},None
for i in range(n):
    order=input().split()
    if order[0]=="print":
        In_order(root);print()
        Pre_order(root);print()
    elif order[0]=="find":
        if find(root,int(order[1])) is not None:print("yes")
        else:print("no")
    elif order[0]=="delete":
        delete(tree,int(order[1]))
    elif order[0]=="insert":
        num=int(order[1])
        if root is None:
            root=num
            tree[root]=[None,None]
        else:
            tree[num]=[None,None]
            insert(tree,num)

Solution (Python):


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

def insert(root, z):
    y = None
    x = None
    if root != None:
        x = root
        
    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
    elif z.key < y.key:
        y.left = z
    else:
        y.right = z

def find(x, k):
    while x != None and k != x.key:
        if k < x.key:
            x = x.left
        else:
            x = x.right
    return x
    
def delete(root, 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:
        root = x
    elif y == y.parent.left:
        y.parent.left = x
    else:
        y.parent.right = x
    
    if y != z:
        z.key = y.key

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 printInOrder(z):
    if z == None:
        return
    if z.left != None:
        printInOrder(z.left)
    inorder.append(str(z.key))
    
    if z.right != None:
        printInOrder(z.right)
        
def printPreOrder(z):
    if z == None:
        return
    
    preorder.append(str(z.key))
    if z.left != None:
        printPreOrder(z.left)
    if z.right != None:
        printPreOrder(z.right)

root = None


n = int(input())
for i in range(n):
    command = input()
    if command[0] == "i":
        com,num = command.split()
        z = Node(int(num))
        insert(root, z)
        if root == None:
            root = z
    elif command[0] == "f":
        com,num = command.split()
        z = Node(int(num))
        x = find(root, int(z.key))
        if x != None:
            print("yes")
        else:
            print("no")
    
    elif command[0] =="d":
        com,num = command.split()
        z = Node(int(num))
        delete(root, find(root, int(z.key)))
    

    else:
        inorder = []
        printInOrder(root)
        print(" ", end = "")
        print(' '.join(inorder))
        preorder = []
        printPreOrder(root)
        print(" ", end = "")
        print(' '.join(preorder))

Solution (Python):
class BinarySearchTree:
    def __init__(self):
        self.lcs = {}
        self.rcs = {}
        self.preorder = []
        self.inorder = []
        self.root = None

    def insert(self, key):
        if self.root is None:
            self.root = key
            self.lcs[key] = None
            self.rcs[key] = None
            return
        parent = self.root
        while True:
            if key < parent:
                if self.lcs[parent] is None:
                    self.lcs[parent] = key
                    self.lcs[key] = None
                    self.rcs[key] = None
                    break
                else:
                    parent = self.lcs[parent]
            else:
                if self.rcs[parent] is None:
                    self.rcs[parent] = key
                    self.lcs[key] = None
                    self.rcs[key] = None
                    break
                else:
                    parent = self.rcs[parent]

    def _find(self, key, cur):
        if key == cur:
            return True
        elif key < cur:
            if self.lcs[cur] is None:
                return False
            else:
                return self._find(key, self.lcs[cur])
        else:
            if self.rcs[cur] is None:
                return False
            else:
                return self._find(key, self.rcs[cur])

    def find(self, key):
        return self._find(key, self.root)

    def _search(self, cur):
        self.preorder.append(cur)
        if self.lcs[cur]:
            self._search(self.lcs[cur])
        self.inorder.append(cur)
        if self.rcs[cur]:
            self._search(self.rcs[cur])

    def print(self):
        self.preorder = []
        self.inorder = []
        self._search(self.root)
        print(' ' + ' '.join(map(str, self.inorder)))
        print(' ' + ' '.join(map(str, self.preorder)))

    def _delete(self, key, cur, parent):
        if key == cur:
            if self.lcs[cur] is None:
                
                if self.lcs[parent] == cur:
                    self.lcs[parent] = self.rcs[cur]
                else:
                    self.rcs[parent] = self.rcs[cur]
            elif self.rcs[cur] is None:
                
                if self.lcs[parent] == cur:
                    self.lcs[parent] = self.lcs[cur]
                else:
                    self.rcs[parent] = self.lcs[cur]
            else:
                
                n = self.inorder[self.inorder.index(key) + 1]
                self._delete(n, cur, parent)
                self.lcs[n], self.rcs[n] = self.lcs[cur], self.rcs[cur]
                self.lcs[cur], self.rcs[cur] = None, None
                if key == self.root:
                    self.root = n
                elif self.lcs[parent] == cur:
                    self.lcs[parent] = n
                else:
                    self.rcs[parent] = n
            return True
        elif key < cur:
            if self.lcs[cur] is None:
                return False
            else:
                return self._delete(key, self.lcs[cur], cur)
        else:
            if self.rcs[cur] is None:
                return False
            else:
                return self._delete(key, self.rcs[cur], cur)

    def delete(self, key):
        self.preorder = []
        self.inorder = []
        self._search(self.root)
        self._delete(key, self.root, None)


T = BinarySearchTree()
N = int(input())
for _ in range(N):
    s = input().split()
    if s[0] == 'insert':
        T.insert(int(s[1]))
    elif s[0] == 'find':
        print('yes' if T.find(int(s[1])) else 'no')
    elif s[0] == 'delete':
        T.delete(int(s[1]))
    else:
        T.print()

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
        self.list = []
    
    def insert(self, node_tobe_added):
            y = None 
            x = self.root
            while x != None:
                
                y = x
                if node_tobe_added.key < x.key:
                    x = x.left
                else:
                    x = x.right
            
            node_tobe_added.parent = y 
            
            
            if y == None:
                self.root = node_tobe_added
            elif node_tobe_added.key < y.key:
                
                y.left = node_tobe_added
            else:
                
                y.right = node_tobe_added
                
    def find(self, key):
        x = self.root
        while x != None and key != x.key:
            if key < x.key:
                x = x.left
            else:
                x = x.right
        return x
    
    def delete(self, node):
        if node.left == None or node.right == None:
            y = node
        else:
            y = self.get_successor(node)
        
        if y.left != None:
            x = y.left
        else:
            x = y.right
        
        if x != None:
            x.parent = y.parent
        
        if y.parent == None:
            self.root = x
        elif y == y.parent.left:
            y.parent.left = x
        else:
            y.parent.right = x
        
        if y != node:
            node.key = y.key
        
    def get_successor(self, node):
        if node.right != None:
            return self.get_minimum(node.right)
        
        y = node.parent
        while y != None and node == y.right:
            node = y
            y = y.parent
        return y
    
    def get_minimum(self, node):
        while node.left != None:
            node = node.left
        return node
    
    def pre_parse(self, node):
        if node == None:
            return
        self.list.append(node.key)
        self.pre_parse(node.left)
        self.pre_parse(node.right)
    
    def in_parse(self, node):
        if node == None:
            return
        self.in_parse(node.left)
        self.list.append(node.key)
        self.in_parse(node.right)

T = Tree()

N = int(input())
for i in range(N):
        order, *key = input().split() 
        if order == "print":
            T.list = []
            T.in_parse(T.root)
            print(" " + " ".join(map(str, T.list)))
            T.list = []
            T.pre_parse(T.root)
            print(" " + " ".join(map(str, T.list)))
        elif order == "insert":
            T.insert(Node(int(key[0]))) 
        elif order == "find":
            if T.find(int(key[0])):
                print("yes")
            else:
                print("no")
        else:
            node = T.find(int(key[0]))
            T.delete(node)

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

class BinaryTree():
    def __init__(self):
        self.root = None
    
    def insert(self, value):
        if self.root == None:
            self.root = Node(value)
        else:
            parentnode = curnode = self.root
            while curnode != None:
                parentnode = curnode
                if curnode.value > value:
                    curnode = curnode.left
                else:
                    curnode = curnode.right
            if value > parentnode.value:
                parentnode.right = Node(value)
            else:
                parentnode.left = Node(value)

    def find(self, value):
        c, _ = self.findvalue(value)
        if c is None:
            return False
        else:
            return True

    def findvalue(self, value):
        parentnode = curnode = self.root
        while curnode != None:
            if value == curnode.value:
                return curnode, parentnode
            parentnode = curnode
            if value > curnode.value:
                curnode = curnode.right
            else:
                curnode = curnode.left
        return None, None
    
    def replace_child(self, parentnode, childnode, newnode):
        if parentnode == self.root:
            self.root = newnode
        elif parentnode.value > childnode.value:
            parentnode.left = newnode
        else:
            parentnode.right = newnode
    
    def delete(self, value):
        curnode, parentnode = self.findvalue(value)
        if curnode is None:
            return False
        if curnode.left == None and curnode.right == None:
            self.replace_child(parentnode, curnode, None)
        elif curnode.right == None:
            self.replace_child(parentnode, curnode, curnode.left)
        elif curnode.left == None:
            self.replace_child(parentnode, curnode, curnode.right)
        else:
            p = curnode
            r = curnode.right
            while r.left != None:
                p = r
                r = r.left
            curnode.value = r.value
            self.replace_child(p, r, r.right)


    def preorder(self, root):
        if root == None:
            pass
        else:
            print(' %d' % root.value, end='')
            self.preorder(root.left)
            self.preorder(root.right)

    def inorder(self, root):
        if root == None:
            pass
        else:
            self.inorder(root.left)
            print(' %d' % root.value, end='')
            self.inorder(root.right)

if __name__ == '__main__':
    n = int(input())
    binarytree = BinaryTree()
    for _ in range(n):
        common = input()
        if common[0] == 'i':
            binarytree.insert(int(common[7:]))
        elif common[0] == 'f':
            if binarytree.find(int(common[5:])):
                print('yes')
            else:
                print('no')
        elif common[0] == 'd':
            binarytree.delete(int(common[7:]))
        else:
            binarytree.inorder(binarytree.root)
            print()
            binarytree.preorder(binarytree.root)
            print()

Solution (Python):

class Node:
    key = None
    parent = None
    left = None
    right = None

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


def insert(key):
    global T
    global root

    new_node = Node(key)
    T.append(new_node)

    if root is None:
        root = new_node

    else:
        y = None  
        x = root  

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

        new_node.parent = y
        if new_node.key < y.key:
            y.left = new_node
        else:
            y.right = new_node


def find(key):
    global T
    global root

    x = root

    while x is not None and key != x.key:
        

        if key < x.key:
            x = x.left
        else:
            x = x.right
    return x  


def delete(key):
    global T
    global root

    z = find(key)


    
    if z.left is None or z.right is None:
        y = z
    else:
        y = tree_successor(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  
    else:
        if y == y.parent.left:
            y.parent.left = x  
        else:
            y.parent.right = x

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


def tree_minimum(x):
    """ xを根とした場合に、一番小さなノードを見つける（＝左下に行き続ける） """
    while x.left is not None:
        x = x.left
    return x


def tree_successor(x):
    """ 中間巡回でxの次に来るものを見つける。
        中間巡回は昇順ソートと同じなので、つまり、
        xの次に大きいノードを探すということ。

        もしxに右の子がいれば、x以下の木のなかで、
        xの次に大きいノードを見つけることができる。

        しかし、もしxが右の子を持たなければ、
        全体の木の中で次に大きいのは、
        xより上の木まで探しに行く必要がある。
    """

    """ xに右の子がいる場合 """
    if x.right is not None:
        return tree_minimum(x.right)

    """ xに右の子がいない場合 """
    y = x.parent  

    
    while y is not None and x == y.right:
        x = y
        y = y.parent

    return y


def in_order(node, order):
    if node is None:
        return

    in_order(node.left, order)
    order.append(node.key)
    in_order(node.right, order)


def pre_order(node, order):
    if node is None:
        return

    order.append(node.key)
    pre_order(node.left, order)
    pre_order(node.right, order)


m = int(input())
T = []
root = None

for i in range(m):
    order = input()

    if order.startswith('print'):
        output = []
        in_order(root, output)
        
        print(' ' + ' '.join(map(str, output)))

        output = []
        pre_order(root, output)
        
        print(' ' + ' '.join(map(str, output)))

    elif order.startswith('find'):
        order, value = order.split()
        value = int(value)
        _ = find(value)
        if _ is None:
            print('no')
        else:
            print('yes')

    elif order.startswith('delete'):
        order, value = order.split()
        value = int(value)
        delete(value)

    else:
        order, value = order.split()
        value = int(value)
        insert(value)

Solution (Python):
import sys
class Tree():
    def __init__(self):
        self.root = None
    def insert(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 find(self, key):
        x = self.root
        while x and x.key != key:
            if x.key < key:
                x = x.right
            else:
                x = x.left
        return x
    def delete(self, key):
        z = self.find(key)
        y = self.successor(z) if z.left and z.right else z
        x = y.left if y.left else y.right

        if x:
            x.parent = y.parent
        if y.parent == None:
            self.root = x 
        elif y == y.parent.left:
            y.parent.left = x
        else:
            y.parent.right = x
        if y != z:
            z.key = y.key
    def successor(self, x):
        if x.right:
            return self.minimum(x.right)
        y = x.parent
        while y and x == y.right:
            x = y
            y = y.parent
        return y

    def minimum(self, x):
        while x.left:
            x = x.left
        return x
    
    def print(self):
        print('',' '.join(map(str, self.root.inwalk())))
        print('',' '.join(map(str, self.root.prewalk())))
    
class Node():
    def __init__(self, key):
        self.key = key
        self.parent = self.left = self.right = None
    def prewalk(self):
        ret = [self.key]
        if self.left:
            ret += self.left.prewalk()
        if self.right:
            ret += self.right.prewalk()
        return ret
    def inwalk(self):
        ret = []
        if self.left:
            ret += self.left.inwalk()
        ret += [self.key]
        if self.right:
            ret += self.right.inwalk()
        return ret
tree = Tree()
n = sys.stdin.readline()
for line in sys.stdin:
    if line[0] == 'i':
        tree.insert(int(line.split()[1]))
    elif line[0] == 'f':
        print('yes' if tree.find(int(line.split()[1])) else 'no')
    elif line[0] == 'd':
        tree.delete(int(line.split()[1]))            
    else:
        tree.print()

Solution (Python):
class node:
    def __init__(self, key):
        self.k = key
        self.p = None
        self.l = None
        self.r = None

def preParse(u):
    if u == None:
        return
    print(" " + str(u.k), end = '')
    preParse(u.l)
    preParse(u.r)

def inParse(u):
    if u == None:
        return
    inParse(u.l)
    print(" " + str(u.k), end = '')
    inParse(u.r)

def postParse(u):
    if u == None:
        return
    postParse(u.l)
    postParse(u.r)
    print(" " + str(u.k), end = '')

root = None
def insert(k):
    global root
    parent = None
    u = root
    z = node(k)
    while u != None:
        parent = u
        if z.k < u.k:
            u = u.l
        else:
            u = u.r

    z.p = parent
    if parent == None:
        root = z
    elif z.k < parent.k:
        parent.l = z
    else:
        parent.r = z

def find(k):
    global root
    u = root
    while u != None and u.k != k:
        if k < u.k:
            u = u.l
        else:
            u = u.r
    return u

def delete (k):
    global root
    u = find(k)
    if u.l == None or u.r == None:
        y = u
    else:
        y = getSuccessor(u)

    if y.l != None:
        x = y.l
    else:
        x = y.r

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

    if y.p == None:
        root = x
    elif y == y.p.l:
        y.p.l = x
    else:
        y.p.r = x

    if y != u:
        u.k = y.k

def getSuccessor(z):
    if z.r != None:
        return getMinimum(z.r)
    
    y = z.p
    while y != None and z == y.r:
        z = y
        y = y.p
    return y

def getMinimum(z):
    while z.l != None:
        z = z.l
    return z

n = int(input())
cmdList = [input() for _ in range(n)]

for cmd in cmdList:
    if cmd[0] == "p":
        inParse(root)
        print("")
        preParse(root)
        print("")
    elif cmd[0] == "f":
        print("no" if find(int(cmd[5:])) == None else "yes")
    elif cmd[0] == "d":
        a = 1
        delete(int(cmd[7:]))
    else:
        insert(int(cmd[7:]))

Solution (Python):
class Node():
    """節クラス: valは節の値, parent/left/rightはそれぞれ親/左側の子/右側の子へのポインタを表す"""
    def __init__(self, val):
        self.val = val
        self.parent = None
        self.right = None
        self.left = None


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

    def search(self, val: int) -> bool:
        """二分木に値valを持つ節が存在するかどうか判定する
        根から順番に子を辿っていき、valと一致する節が存在する場合はTrue、存在しない場合はFalseを返す
        """
        ptr = self.root
        while ptr is not None:
            if ptr.val == val:
                return True
            if val < ptr.val:
                ptr = ptr.left
            else:
                ptr = ptr.right
        return False 

    def insert(self, val: int):
        """二分木に値valを持つ節を追加する（すでに二分木内に同じ要素が存在している場合も追加する）
        根から順番に子を辿っていき、ポインタが示す先に節が存在しなくなったらNode(val)として節を追加する
        """
        if self.root is None:
            
            self.root = Node(val)
            return

        ptr = self.root 
        while True:
            if val < ptr.val:
                if ptr.left is None:
                    
                    ptr.left = Node(val)
                    ptr.left.parent = ptr
                    return
                ptr = ptr.left
            else:
                if ptr.right is None:
                    
                    ptr.right = Node(val)
                    ptr.right.parent = ptr
                    return
                ptr = ptr.right
        
    def delete(self, val: int):
        """二分木から値valを持つ節を削除する
        根から順番に子を辿っていき、ptr.val == val が見つかったらptrをつなぎ替える。
        """
        if self.root is None:
            
            return 
        
        ptr = self.root
        
        while True: 
            if ptr is None:
                return
            if ptr.val == val:
                break
            elif val < ptr.val:
                ptr = ptr.left
            else:
                ptr = ptr.right
       
        
        if ptr.left is None and ptr.right is None:
            if ptr.parent.left == ptr:
                ptr.parent.left = None
            else:
                ptr.parent.right = None
        
        elif ptr.left is None:
            if ptr.parent.left == ptr:
                ptr.parent.left = ptr.right
                ptr.right.parent = ptr.parent
            else:
                ptr.parent.right = ptr.right
                ptr.right.parent = ptr.parent
        
        elif ptr.right is None:
            if ptr.parent.left == ptr:
                ptr.parent.left = ptr.left
                ptr.left.parent = ptr.parent
            else:
                ptr.parent.right = ptr.left
                ptr.left.parent = ptr.parent
        
        else:
            s = self.search_min(ptr.right)
            ptr.val = s.val
            if s.parent.left == s:
                s.parent.left = None
            else:
                s.parent.right = None            
    
    def search_min(self, ptr):
        """ptrを部分木の根としたときのptrの最小値の節へのポインタを返す
        ptr.leftをひたすら辿っていくことで可能"""
        while True:
            if ptr.left is None:
                return ptr
            ptr = ptr.left
            
    def rotate_left(self, ptr):
        """木を左回転する"""
        w = ptr.right
        w.parent = ptr.parent
        if w.parent is not None:
            if w.parent.left == ptr:
                w.parent.left = w
            else:
                w.parent.right = w
        ptr.right = w.left
        if ptr.right is not None:
            ptr.right.parent = ptr
        ptr.parent = w
        w.left = ptr
        if ptr == self.root:
            self.root = w
            self.root.parent = None

 
    def rotate_right(self, ptr):
        """木を右回転する"""
        w = ptr.left
        w.parent = ptr.parent
        if w.parent is not None:
            if w.parent.right == ptr:
                w.parent.right = w
            else:
                w.parent.left = w
        ptr.left = w.right
        if ptr.left is not None:
            ptr.left.parent = ptr
        ptr.parent = w
        w.right = ptr
        if ptr == self.root:
            self.root = w
            self.root.parent = None

    def preorder_tree_walk(self, ptr, res):
        """先行順巡回(preorder tree walk)"""
        if ptr is None:
            return res
        res.append(ptr.val)
        if ptr.left is not None:
            self.preorder_tree_walk(ptr.left, res)
        if ptr.right is not None:
            self.preorder_tree_walk(ptr.right, res)
        return res

    def inorder_tree_walk(self, ptr, res):
        """中間順巡回(inorder tree walk)"""
        if ptr is None:
            return res
        if ptr.left is not None:
            self.inorder_tree_walk(ptr.left, res)
        res.append(ptr.val)
        if ptr.right is not None:
            self.inorder_tree_walk(ptr.right, res)
        return res

    def postorder_tree_walk(self, ptr, res):
        """後行順巡回(postorder tree walk)"""
        if ptr is None:
            return res
        if ptr.left is not None:
            self.inorder_tree_walk(ptr.left, res)
        if ptr.right is not None:
            self.inorder_tree_walk(ptr.right, res)
        res.append(ptr.val)
        return res
      
      
n = int(input())
info = [list(input().split()) for i in range(n)]
bt = BinaryTree()

for i in range(n):
    if info[i][0] == "insert":
        if bt.search(int(info[i][1])):
            continue
        else:
            bt.insert(int(info[i][1]))
    elif info[i][0] == "find":
        if bt.search(int(info[i][1])):
            print("yes")
        else:
            print("no")
    elif info[i][0] == "delete":
        bt.delete(int(info[i][1]))
    else:
        print(" ", end="")
        print(*bt.inorder_tree_walk(bt.root, res=[]))
        print(" ", end="")
        print(*bt.preorder_tree_walk(bt.root, res=[]))