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

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

    def insert(self, key):
        root_node = self.root
        insert_node = Node(key)
        parent_node = None

        while root_node:
            parent_node = root_node
            if insert_node.key < root_node.key:
                root_node = root_node.left
            else:
                root_node = root_node.right
            
        insert_node.parent = parent_node

        if parent_node == None:
            self.root = insert_node
        elif insert_node.key < parent_node.key:
            parent_node.left = insert_node
        else:
            parent_node.right = insert_node
        
    def find(self, key):
        node = self.root

        while node:
            if node.key == key:
                return node
            elif node.key < key:
                node = node.right
            else:
                node = node.left 

        return None

    def delete(self, key):
        node = self.find(key)

        if node == None:
            return 
        
        if node.left and node.right:
            next_node = node.right

            while next_node.left:
                next_node = next_node.left

            node.key = next_node.key
            node = next_node

        if node.left:
            node.left.parent = node.parent
            if node.parent.left == node:
                node.parent.left = node.left
            else:
                node.parent.right = node.left
        elif node.right:
            node.right.parent = node.parent
            if node.parent.left == node:
                node.parent.left = node.right
            else:
                node.parent.right = node.right
        else:
            if node.parent.left == node:
                node.parent.left = None
            else:
                node.parent.right = None

    def show_inorder(self, node):
        if node == None:
            return 
        self.show_inorder(node.left)
        print(' ' + str(node.key), end = '')
        self.show_inorder(node.right)

    def show_preorder(self, node):
        if node == None:
            return 
        print(' ' + str(node.key), end = '')
        self.show_preorder(node.left)
        self.show_preorder(node.right)

tree = BinarySearchTree()
n = int(input())

for i in range(n):
    command = input().split()

    if command[0] == 'insert':
        tree.insert(int(command[1]))
    elif command[0] == 'find':
        a = tree.find(int(command[1]))
        if a != None:
            print('yes')
        else:
            print('no')        
    elif command[0] == 'delete':
        tree.delete(int(command[1]))
    elif command[0] == 'print':
        tree.show_inorder(tree.root)
        print()
        tree.show_preorder(tree.root)
        print()

Solution (Python):
if __name__ == '__main__':
    import sys
    input = sys.stdin.readline

    NIL = -1

    m = int(input())

    root = NIL

    def insert(k):
        global root
        y = NIL
        x = root
        z = {'key':k, 'left':NIL, 'right':NIL}
        while x != NIL:
            y = x
            if z['key'] < x['key']:
                x = x['left']
            else:
                x = x['right']
        z['parent'] = y

        if y == NIL:
            root = z
        elif z['key'] < y['key']:
            y['left'] = z
        else:
            y['right'] = z

    def find(u, k):
        while u != NIL and k != u['key']:
            if k < u['key']:
                u = u['left']
            else:
                u = u['right']
        return u

    def tree_minimum(x):
        while x['left'] != NIL:
            x = x['left']
        return x

    def tree_successor(x):
        if x['right'] != NIL:
            return tree_minimum(x['right'])
        y = x['parent']
        while y != NIL and x == y['right']:
            x = y
            y = y['parent']
        return y

    def tree_delete(z):
        global root
        if z['left'] == NIL or z['right'] == NIL:
            y = z
        else:
            y = tree_successor(z)
        
        if y['left'] != NIL:
            x = y['left']
        else:
            x = y['right']

        if x != NIL:
            x['parent'] = y['parent']

        if y['parent'] == NIL:
            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(u):
        if u == NIL:
            return
        inorder(u['left'])
        print(' ' + str(u['key']), end='')
        inorder(u['right'])

    def preorder(u):
        if u == NIL:
            return
        print(' ' + str(u['key']), end='')
        preorder(u['left'])
        preorder(u['right'])

    for _ in range(m):
        command = input()
        if command[0] == 'f':
            _, x = command.split()
            x = int(x)
            t = find(root, x)
            if t != NIL:
                print('yes')
            else:
                print('no')
        elif command[:6] == 'insert':
            _, x = command.split()
            x = int(x)
            insert(x)
        elif command[:5] == 'print':
            inorder(root)
            print('')
            
            preorder(root)
            print('')
        else:
            _, x = command.split()
            x = int(x)
            tree_delete(find(root, x))

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

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

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

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

    def delete1(self, node):
        y = node.parent
        if y.key < node.key:
          y.right = None
        elif y.key > node.key:
          y.left = None
        node.parent = None

    def delete2(self, node):
        y = node.parent
        if y.key < node.key:
          y.right = node.right
        else:
          y.left = node.right
        node.right.parent = y

    def delete3(self, node):
        y = node.parent
        if y.key < node.key:
          y.right = node.left
        else:
          y.left = node.left
        node.left.parent = y
    
    def delete4(self, node):
        y = node.right
        x = y
        while x.left:
          x = x.left

        node.key = x.key
        if y == x:
          node.right = None
          
        if not x.left and not x.right:
          self.delete1(x)
        elif not x.left and x.right:
          self.delete2(x)
        else:
          self.delete3(x)

    def delete(self, node):
        y = self.find(node)
        if y:
          if not y.left and not y.right:
             self.delete1(y)

          elif not y.left and y.right:
             self.delete2(y)
        
          elif y.left and not y.right:
             self.delete3(y)

          else:
             self.delete4(y)

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

    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().split()
    if len(l) == 2 and l[0] == "insert":
       tree.insert(Node(int(l[1])))
    elif len(l) == 2 and l[0] == "find":
       y = tree.find(Node(int(l[1])))
       if y:
          print("yes")
    elif len(l) == 2 and l[0] == "delete":
       tree.delete(Node(int(l[1])))
    else:
       tree.print()
    m -= 1

Solution (Python):
import sys
input = sys.stdin.readline
print = sys.stdout.write

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

class BinarySearchTree:
    __slots__ = ["root"]
    def __init__(self):
        self.root = None
    
    def insert(self, data):
        parent = self.root
        if parent is None:
            self.root = Node(data)
            return
        while parent:
            parent_old = parent
            parent = parent.left if data < parent.data else parent.right
        if data < parent_old.data:
            parent_old.left = Node(data)
        else:
            parent_old.right = Node(data)
        
    def find(self, data):
        parent = self.root
        if parent is None:
            print("no\n")
            return
        while parent:
            if parent.data == data:
                print("yes\n")
                return
            parent = parent.left if data < parent.data else parent.right
        print("no\n")
        return
    
    def delete(self, data):
        target = self.root
        if target is None:
            return
        while target:
            if target.data == data:
                if target.right and target.left:
                    next_target = target.right
                    if next_target.left is None:
                        if target == self.root:
                            self.root = next_target
                        target.data = next_target.data
                        target.right = next_target.right
                        return
                    while next_target.left:
                        parent = next_target
                        next_target = next_target.left
                    if target == self.root:
                        self.root = next_target
                    target.data = next_target.data
                    parent.left = next_target.right
                    return
                else:
                    child = target.right or target.left
                    if target == self.root:
                        self.root = child
                        if child is None:
                            return
                    if child:
                        target.data, target.left, target.right = child.data, child.left, child.right
                    else:
                        if data < parent.data:
                            parent.left = None
                        else:
                            parent.right = None
                    return
            parent = target
            target = target.left  if data < target.data else target.right


def print_preorder(node):
    print(" {}".format(node.data))
    if node.left:
        print_preorder(node.left)
    if node.right:
        print_preorder(node.right)

def print_inorder(node):
    if node.left:
        print_inorder(node.left)
    print(" {}".format(node.data))
    if node.right:
        print_inorder(node.right)

if __name__ == "__main__":
    n = int(input())
    binary_search_tree = BinarySearchTree()
    for _ in range(n):
        operation, *num = input().split()
        if operation[0] == "i":
            binary_search_tree.insert(int(num[0]))
        elif operation[0] == "f":
            binary_search_tree.find(int(num[0]))
        elif operation[0] == "d":
            binary_search_tree.delete(int(num[0]))
        elif binary_search_tree.root is not None:
            print_inorder(binary_search_tree.root)
            print("\n")
            print_preorder(binary_search_tree.root)
            print("\n")

Solution (Python):
def preParse(u):
    if u == None:
        return
    print(' {}'.format(u), end='')
    preParse(nodes[u][1])
    preParse(nodes[u][2])

def inParse(u):
    if u == None:
        return
    inParse(nodes[u][1])
    print(' {}'.format(u), end='')
    inParse(nodes[u][2])

def printTree(root):
    inParse(root)
    print()
    preParse(root)
    print()

def insert(nodes,z,root):
    x = root
    y = None
    while x != None:
        y = x
        if z < x:
            x = nodes[x][1]
        else:
            x = nodes[x][2]
    nodes[z][0] = y

    if y == None:
        root = z
    elif z < y:
        nodes[y][1] = z
    else:
        nodes[y][2] = z
    return root

def find(nodes,z,root):
    x = root
    while x != None and z != x:
        if z < x:
            x = nodes[x][1]
        else:
            x = nodes[x][2]
    return x

def getMinimum(nodes,x):
    while nodes[x][1] != None:
        x = nodes[x][1]
    return x

def getSuccessor(nodes,x):
    if nodes[x][2] != None:
        return getMinimum(nodes,nodes[x][2])
    
    y = nodes[x][0]
    while y != None and z == nodes[y][2]:
        x = y
        y = nodes[y][0]
    return y

def deleteNode(nodes,z,root):
    
    if nodes[z][1] == None or nodes[z][2] == None:
        y = z
    else:
        y = getSuccessor(nodes,z)

    
    if nodes[y][1] != None:
        x = nodes[y][1]
    else:
        x = nodes[y][2]

    
    if x != None:
        nodes[x][0] = nodes[y][0]

    
    if nodes[y][0] == None:
        root = x
    
    elif y == nodes[nodes[y][0]][1]:
        nodes[nodes[y][0]][1] = x
    
    else:
        nodes[nodes[y][0]][2] = x
    
    
    
    
    if y != z:
        nodes[y] = nodes[z]
        if nodes[y][0] != None:
            if nodes[nodes[y][0]][1] == z:
                nodes[nodes[y][0]][1] = y
            else:
                nodes[nodes[y][0]][2] = y
        if nodes[y][1] != None:
            nodes[nodes[y][1]][0] = y
        if nodes[y][2] != None:
            nodes[nodes[y][2]][0] = y

    return root


nodes = {}



N = int(input())

root = None

for i in range(N):
    order = input().split()
    if order[0] == 'print':
        printTree(root)
        continue

    z = int(order[1])
    if order[0] == 'insert':
        nodes[z] = [None,None,None]
        root = insert(nodes,z,root)
        continue

    if order[0] == 'find':
        k = find(nodes,z,root)
        if k == z:
            print('yes')
        else:
            print('no')
        continue

    if order[0] == 'delete':
        root = deleteNode(nodes,z,root)
        continue

Solution (Python):
class BinarySearchTree:
    def __init__(self):
        self.root = None
        self.order_list = []
    def insert(self, z):
        y = None
        x = self.root
        while x != None:
            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 != None:
            if key == x.key:
                return x
            elif key < x.key:
                x = x.left
            else:
                x = x.right
        return None
    def delete(self, z):
        if z.left == None and z.right == None:
            if z.key < z.parent.key:
                z.parent.left = None
            else:
                z.parent.right = None
        elif z.left != None and z.right == None:
            z.left.parent = z.parent
            if z.key < z.parent.key:
                z.parent.left = z.left
            else:
                z.parent.right = z.left
        elif z.left == None and z.right != None:
            z.right.parent = z.parent
            if z.key < z.parent.key:
                z.parent.left = z.right
            else:
                z.parent.right = z.right
        else:
            next_node = z.right
            while next_node.left:
                next_node = next_node.left
            z.key = next_node.key
            self.delete(next_node)
            
    def walk_preorder(self, node):
        if node == None:
            return None
        self.order_list.append(node.key)
        self.walk_preorder(node.left)
        self.walk_preorder(node.right)
    def walk_inorder(self, node):
        if node == None:
            return None
        self.walk_inorder(node.left)
        self.order_list.append(node.key)
        self.walk_inorder(node.right)
    def print_nodes(self):
        self.order_list = []
        self.walk_inorder(self.root)
        inorder_str = ' '.join(map(str, self.order_list))
        print(' {}'.format(inorder_str))
        self.order_list = []
        self.walk_preorder(self.root)
        preorder_str = ' '.join(map(str, self.order_list))
        print(' {}'.format(preorder_str))
        
class Node:
    def __init__(self, key):
        self.key = key
        self.parent = None
        self.left = None
        self.right = None

n = int(input())
tree = BinarySearchTree()
for _ in range(n):
    command = input().split(' ')
    if len(command) == 1:
        tree.print_nodes()
    else:
        opecode, operand = command[0], int(command[1])
        if opecode == 'insert':
            node = Node(operand)
            tree.insert(node)
        elif opecode == 'find':
            node = tree.find(operand)
            if node != None:
                print('yes')
            else:
                print('no')
        elif opecode == 'delete':
            node = tree.find(operand)
            if node != None:
                tree.delete(node)

Solution (Python):
"""
ALDS1_8_C
螺旋本を参考にしています
"""
import copy

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

class Tree:
    def insert_root_node(self, new_id):
        global root_node 
        root_node = Node(new_id)

    def insert_node(self, new_id): 
        compare_node = root_node 
        new_node = Node(new_id)
        while compare_node is not None: 
            new_node.parent = compare_node 
            if compare_node.node_id < new_id:
                compare_node = compare_node.right
            else:
                compare_node = compare_node.left

        if new_node.parent.node_id < new_id:
            new_node.parent.right = new_node
        else:
            new_node.parent.left = new_node


    def find(self, search_id):
        tmp_node = root_node
        while tmp_node:
            if tmp_node.node_id == search_id:
                print('yes')
                return
            elif tmp_node.node_id < search_id:
                tmp_node = tmp_node.right
            else:
                tmp_node = tmp_node.left
        print('no')

    
    def getTheLeft(self, search_node): 
        while search_node.left:
            search_node = search_node.left
        return search_node

    def delete(self, search_id):
        tmp_node = root_node
        while tmp_node:
            if tmp_node.node_id == search_id:
                if tmp_node.left is None and tmp_node.right is None:
                    if tmp_node.parent.node_id < search_id:
                        tmp_node.parent.right = None
                    else:
                        tmp_node.parent.left = None
                    return
                elif tmp_node.left is None and tmp_node.right is not None:
                    tmp_node.right.parent = tmp_node.parent
                    if tmp_node.parent.node_id < search_id:
                        tmp_node.parent.right = tmp_node.right
                    else:
                        tmp_node.parent.left = tmp_node.right
                    return
                elif tmp_node.left is not None and tmp_node.right is None:
                    tmp_node.left.parent = tmp_node.parent
                    if tmp_node.parent.node_id < search_id:
                        tmp_node.parent.right = tmp_node.left
                    else:
                        tmp_node.parent.left = tmp_node.left
                    return
                else:
                    left_node = tmp_node.right
                    left_node = self.getTheLeft(left_node) 
                    if left_node.parent.node_id < left_node.node_id: 
                        left_node.parent.right = None
                        left_node.parent = None
                    else:
                        left_node.parent.left = None
                        left_node.parent = None
                    tmp_node.node_id = left_node.node_id
                    return

            elif tmp_node.node_id < search_id:
                tmp_node = tmp_node.right
            else:
                tmp_node = tmp_node.left


def inParse(tmp_node):
    if not tmp_node:
        return
    inParse(tmp_node.left)
    print(' '+str(tmp_node.node_id), end='')
    inParse(tmp_node.right)
        
def preParse(tmp_node):
    if not tmp_node:
        return
    print(' '+str(tmp_node.node_id), end='')
    preParse(tmp_node.left)
    preParse(tmp_node.right)




tree = Tree()

n = int(input())
root_id = 0
root_node = None
for i in range(n):
    order = input().split()
    if not root_node: 
        root_id = int(order[1])
        tree.insert_root_node(int(order[1]))
    elif order[0][0] == 'i':
        new_id = int(order[1])
        tree.insert_node(new_id)
    elif order[0][0] == 'p':
        node = copy.copy(root_node)
        inParse(node)
        print()
        node = copy.copy(root_node)
        preParse(node)
        print()
    elif order[0][0] == 'f':
        tree.find(int(order[1]))
    elif order[0][0] == 'd':
        tree.delete(int(order[1]))

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

    def _get_most_left_node(self):
        x = self
        while x.left is not None:
            x = x.left
        return x
    
class Tree():
    def __init__(self, root=None):
        self.root = root
    
    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 is None:   
            self.root = node
        elif node.key < y.key:
            y.left = node
        else:
            y.right = node
    
    def print_inorder_tree_walk(self):
        def work(node):
            if node is None:
                return
            work(node.left)
            print('', node.key, end='')
            work(node.right)

        work(self.root)
        print()
    
    def print_preorder_tree_walk(self):
        def work(node):
            if node is None:
                return
            print('', node.key, end='')
            work(node.left)
            work(node.right)

        work(self.root)
        print()

    def find(self, key):
        """Tree 中に key をもつノードがあればそのノードを返す。なければ None を返す。"""
        x = self.root
        while x is not None:
            if key == x.key:
                return x
            elif key < x.key:
                x = x.left
            else:
                x = x.right
        return None

    def delete(self, key):
        """削除できたら True、存在せず削除できない場合は False を返す。"""
        x = self.find(key)
        if not x:
            return False
        y = x if x.left is None or x.right is None else x.right._get_most_left_node()
        z = y.left if y.left is not None else y.right
        if z is not None: z.parent = y.parent
        if y.parent is None:
            self.root = z
        elif y is y.parent.left:
            y.parent.left = z
        else:
            y.parent.right = z
        
        if x is not y:
            x.key = y.key
        
        return True

if __name__ == '__main__':
    import sys

    n = int(input())
    T = Tree()
    for _ in range(n):
        command, *args = sys.stdin.readline().split()
        if command[0] == 'i':   
            T.insert(Node(int(args[0])))
        elif command[0] == 'f': 
            if T.find(int(args[0])):
                print('yes')
            else:
                print('no')
        elif command[0] == 'd': 
            T.delete(int(args[0]))
        else:   
            T.print_inorder_tree_walk()
            T.print_preorder_tree_walk()

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

    def is_root(self):
        return self.parent is None

    def num_children(self):
        count = 0
        if self.left is not None:
            count += 1
        if self.right is not None:
            count += 1
        return count

    def has_left(self):
        return self.left is not None

    def has_right(self):
        return self.right is not None

    def has_parent(self):
        return self.parent is not None

    def __key(self, obj):
        if isinstance(obj, int):
            return obj
        if isinstance(obj, Node):
            return obj.key

class Tree():
    def __init__(self, num_list=[]):
        self.root = None
        for num in num_list:
            self.insert(num)

    def is_empty(self):
        return self.root is None

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

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

    def __preorder(self, node):
        if node is None:
            return []
        return [node.key] + self.__preorder(node.left) + self.__preorder(node.right)

    def __inorder(self, node):
        if node is None:
            return []
        return self.__inorder(node.left) + [node.key] + self.__inorder(node.right)

    def __postorder(self, node):
        if node is None:
            return []
        return self.__postorder(node.left) + self.__postorder(node.right) + [node.key]

    def preorder(self):
        return self.__preorder(self.root)

    def inorder(self):
        return self.__inorder(self.root)

    def postorder(self):
        return self.__postorder(self.root)

    def get_minimum(self, node):
        target = node
        while target.has_left():
            target = target.left
        return target

    def get_successor(self, node):
        target = node
        if target.has_right():
            return self.get_minimum(target.right)
        else:
            while target.has_parent():
                if target.parent.left is target:
                    return target.parent
                target = target.parent
            return None

    def delete(self, key):
        node = self.find(key)
        if node is None:
            raise ValueError
        if node.num_children() == 2:
            denode = self.get_successor(node)
        else:
            denode = node
        
        if denode.has_left():
            child = denode.left
        else:
            child = denode.right

        
        if child is not None:
            child.parent = denode.parent

        
        if denode.is_root():
            self.root = denode
        elif denode.parent.left == denode:
            denode.parent.left = child
        else:
            denode.parent.right = child

        if denode is not node:
            node.key = denode.key
        del denode

def main():
    n = int(input())
    tree = Tree()
    for _ in range(n):
        operation = input()
        if operation[0] == "i":
            tree.insert(int(operation.split()[1]))
        elif operation[0] == "f":
            if tree.find(int(operation.split()[1])) is None:
                print("no")
            else:
                print("yes")
        elif operation[0] == "d":
            tree.delete(int(operation.split()[1]))
        else:
            print(" {}".format(" ".join(map(str, tree.inorder()))))
            print(" {}".format(" ".join(map(str, tree.preorder()))))


if __name__ == "__main__":
    main()