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 TreeNode():
    def __init__(self):
        self.key = None
        self.parent = None
        self.left = None
        self.right = None
    def inoder(self):
        r=[]
        if self.left:
            r += self.left.inoder()
        r += [self.key]
        if self.right:
            r += self.right.inoder()
        return r
 
    def preoder(self):
        r = [self.key]
        if self.left:
            r += self.left.preoder()
        if self.right:
            r += self.right.preoder()
        return r
 
class BinaryTree():
    def __init__(self):
        self.root = None
 
    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 show(self):
        x = self.root
        print(" " + " ".join(map(str, self.root.inoder())))
        print(" " + " ".join(map(str, self.root.preoder())))
 
    def find(self, key):
        currentNode = self.root
        while currentNode:
            if key == currentNode.key:
                return currentNode
            else:
                if key < currentNode.key:
                    currentNode = currentNode.left
                else:
                    currentNode = currentNode.right
        return False
    def next(self, key):
        return self.min(key.right)
    def min (self, key):
        while key.left is not None:
           key = key.left
        return key
     
    def delete(self, key):
        z = self.find(key)
        if z == False: return
        if z.left and z.right:
            y = self.next(z)
        else:
            y = z
            if z == self.root:
                self.root = None
         
        if z.left:
            x = y.left
        else:
            x = y.right

        if x:
            x.parent = y.parent
        if y.parent is 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

n = int(input())
Tree = BinaryTree()
for i in range(n):
    L = input().split()
    if L[0] == "insert":
        Node = TreeNode()
        Node.key = int(L[1])
        Tree.insert(Node)
    if L[0] =="print":
        Tree.show()
    if L[0] =="find":
        if Tree.find(int(L[1])) == False:
            print("no")
        else:
            print("yes")
    if L[0] =="delete":
        Tree.delete(int(L[1]))

Solution (Python):
import sys

class Node:
    def __init__(self, x):
        self.data = x
        self.left = None
        self.right = None
    
    def insert(node, x):
        if node == None:
            return Node(x)




        elif x < node.data:
            node.left = Node.insert(node.left, x)
        else:
            node.right = Node.insert(node.right, x)
        return node
    
    def find(node, x):
        if node.data == x:
            return True
        elif node.left != None and node.data > x:
            return Node.find(node.left, x)
        elif node.right != None and node.data < x:
            return Node.find(node.right, x)
        else:
            return False
        
    def delete(node, x):
        if node.data == x:
            if (node.left == None) and (node.right == None):
                return None
            elif node.left == None:
                return node.right
            elif node.right == None:
                return node.left
            else:
                
                node.data = Node.serch_min(node.right)
                node.right = Node.delete_min(node.right)
                return node
        elif node.data > x:
            node.left =  Node.delete(node.left, x)
        else:
            node.right = Node.delete(node.right, x)
        return node
        
    def serch_min(node):
        if node.left != None:
            return Node.serch_min(node.left)
        else:
            return node.data
    
    def delete_min(node):
        if node.left == None:
            return node.right
        else:
            node.left = Node.delete_min(node.left)
            return node    
        
    def inorder_print(node):







        s = ""
        if node.left != None:
            s += Node.inorder_print(node.left)
        s += " " + str(node.data)
        if node.right != None:
            s += Node.inorder_print(node.right)
        return s
    def preorder_print(node):







        s = ""
        s += " " + str(node.data)
        if node.left != None:
            s += Node.preorder_print(node.left)    
        if node.right != None:
            s += Node.preorder_print(node.right)
        return s
class BinaryTree:
    def __init__(self):
        self.root = None
    
    def insert(self, x):
        self.root = Node.insert(self.root, x)

    def find(self, x):
        if Node.find(self.root, x):
            print("yes")
        else:
            print("no")
            
    def delete(self, x):
        self.root = Node.delete(self.root, x)
        
    def print_tree(self):






        s = Node.inorder_print(self.root)
        print(s)
        s = Node.preorder_print(self.root)
        print(s)
def main():
    T = BinaryTree()
    m = int(sys.stdin.readline())
    for i in range(m):
        s = sys.stdin.readline().strip()
        if(s == "print"):
            T.print_tree()
        elif s.split()[0] == "find":
            T.find(int(s.split()[1]))
        elif s.split()[0] == "delete":
            T.delete(int(s.split()[1]))
        else:
            z = int(s.split()[1])
            T.insert(z)
        
        

if __name__ == "__main__":
    main()

Solution (Python):
import sys


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

    def preorder(self):
        nodeList = [self.key]
        if self.left:
            nodeList += self.left.preorder()
        if self.right:
            nodeList += self.right.preorder()
        return nodeList

    def inorder(self):
        nodeList = []
        if self.left:
            nodeList += self.left.inorder()
        nodeList += [self.key]
        if self.right:
            nodeList += self.right.inorder()
        return nodeList


class BinaryTree():
    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 is 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 is not None and key != x.key:
            if key < x.key:
                x = x.left
            else:
                x = x.right
        return x

    def delete(self, key):
        z = self.find(key)
        if z is not None:
            if z.left is not None and z.right is not None:
                temp = self.getMinimum(z.right)
                self.delete(temp.key)
                z.key = temp.key
            elif z.left is not None:
                if z.parent is None:
                    self.root = z.left
                    z.left.parent = None
                else:
                    if z.parent.left is z:
                        z.parent.left = z.left
                    else:
                        z.parent.right = z.left
                    z.left.parent = z.parent
            elif z.right is not None:
                if z.parent is None:
                    self.root = z.right
                    z.right.parent = None
                else:
                    if z.parent.left is z:
                        z.parent.left = z.right
                    else:
                        z.parent.right = z.right
                    z.right.parent = z.parent
            else:
                if z.parent is None:
                    self.root = None
                else:
                    if z.parent.left is z:
                        z.parent.left = None
                    else:
                        z.parent.right = None

    def getMinimum(self, node):
        while node.left is not None:
            node = node.left
        return node

    def print(self):
        print(" " + " ".join(map(str, self.root.inorder())))
        print(" " + " ".join(map(str, self.root.preorder())))


if __name__ == "__main__":
    tree = BinaryTree()
    n = int(sys.stdin.readline())
    for inp in sys.stdin.readlines():
        inp = inp.split()
        if inp[0] == "insert":
            tree.insert(int(inp[1]))
        elif inp[0] == "find":
            if tree.find(int(inp[1])) is None:
                print("no")
            else:
                print("yes")
        elif inp[0] == "delete":
            tree.delete(int(inp[1]))
        else:
            tree.print()

Solution (Python):
import sys

def main():
    n = input()
    tree = MyBinaryTree(n)
    for i in range(n):
        cmd = map(str,raw_input().split())
        if cmd[0] == "insert":
            insert(tree,MyNode(int(cmd[1])))
        elif cmd[0] == "print":
            tree.inorder(tree.root)
            print ""
            tree.preorder(tree.root)
            print ""
        elif cmd[0] == "find":
            find(tree,int(cmd[1]))
        elif cmd[0] == "delete":
            delete(tree,int(cmd[1]))
    
    
class MyBinaryTree():
    def __init__(self,num_nodes):
        self.root = None

    def preorder(self,node):
        sys.stdout.write(" {}".format(node.key))
        l = node.left
        r = node.right
        if l is not None:
            self.preorder(l)
        if r is not None:
            self.preorder(r)    

    def inorder(self,node):
        l = node.left
        r = node.right
        if l is not None:
            self.inorder(l)
        sys.stdout.write(" {}".format(node.key))
        if r is not None:
            self.inorder(r)


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


def find(T,key):
    x = T.root
    while x is not None and key != x.key:
        if key < x.key:
            x = x.left
        else:
            x = x.right

    if x is not None:
        print "yes"
    else:
        print "no"


def delete(T,key):
    x = T.root
    where = None
    while x is not None and key != x.key:
        if key < x.key:
            x = x.left
            where = 0
        else:
            x = x.right
            where = 1

    if x is not None:
        if x.left is None:
            if x.right is None:
                if where == 0:
                    x.parent.left = None
                else:
                    x.parent.right = None
            elif where == 0:
                x.parent.left  = x.right
                x.right.parent = x.parent
            else:
                x.parent.right = x.right
                x.right.parent = x.parent
            x = None
        elif x.right is None :
            if where == 0:
                x.parent.left = x.left
                x.left.parent = x.parent
            else:
                x.parent.right = x.left
                x.left.parent  = x.parent
            x = None
        else:
            y = x.right
            where = 1
            while y.left is not None:
                y = y.left
                where = 0

            x.key = y.key
            if y.right is not None:
                y.right.parent = y.parent
                y.parent.left  = y.right
            else:
                if where == 0:
                    y.parent.left = None
                else:
                    y.parent.right = None
            y = None
            
        
class MyNode():
    def __init__(self,key):
        self.key =key
        self.parent = None
        self.left = None
        self.right = None


if __name__ == "__main__":
    main()

Solution (Python):

import sys

YES = "yes"
NO = "no"

class Node:
    def __init__(self, value, p = None, l = None, r = None):
        self.key = value
        self.p = p
        self.left = l
        self.right = r

def chgchild(parent, old, new = None):
    if parent == None:
        return
    else:

        if parent.left == old:
            parent.left = new
        else:
            parent.right = new
        if new != None:
            new.p = parent

def delete(node):
    if node == None:
        return

    if node.left == None:
        chgchild(node.p, node, node.right)
    elif node.right == None:
        chgchild(node.p, node, node.left)
    else:
        ino = []
        inorder(node,ino)
        next = 0
        for i in range(len(ino)):
            if ino[i].key == node.key:
                next = i + 1
                break
        node.key = ino[next].key
        delete(ino[next])

def getroot(x):
    if x.p != None:
        return getroot(x.p)
    return x

def keylist(A):
    B = []
    for i in A:
        B.append(i.key)
    return B

def preorder(x, A):
    if x == None:
        return
    A.append(x)
    preorder(x.left, A)
    preorder(x.right, A)

def inorder(x, A):
    if x == None:
        return
    inorder(x.left, A)
    A.append(x)
    inorder(x.right, A)

def postorder(x, A):
    if x == None:
        return
    postorder(x.left, A)
    postorder(x.right, A)
    A.append(x)

def ptree(root):
    pre = []
    ino = []
    preorder(root, pre)
    inorder(root, ino)
    ap = keylist(pre)
    ip = keylist(ino)
    print(" {}".format(" ".join(map(str,ip))))
    print(" {}".format(" ".join(map(str,ap))))

def find(value, root):
    if root == None:
        return None
    elif value < root.key:
        return find(value,root.left)
    elif value > root.key:
        return find(value,root.right)
    return root

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

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

def main():

    """ ????????? """
    num = int(input().strip())
    istr = sys.stdin.read()
    cmds = list(istr.splitlines())
    root = None
    for i in range(num):
        cmd = cmds[i][0]
        if cmd == "i":
            n = Node(int(cmds[i][7:]))
            root = insert(root, n)
        elif cmd == "f":
            if find(int(cmds[i][5:]),root) == None:
                print(NO)
            else:
                print(YES)
        elif cmd == "p":
            ptree(root)
        elif cmd == "d":
            node = find(int(cmds[i][7:]),root)
            delete(node)

 

if __name__ == '__main__':
    main()

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(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):
        node = self.root
        
        while node:
            if node.key == key:
                return node
            elif node.key > key:
                node = node.left
            else:
                node = node.right
        
        return None
    
    def delete(self, key):
        node = self.find(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 preorder(self, node):
        print(" {}".format(node.key), end = "")
        
        if node.left:
            self.preorder(node.left)
        if node.right:
            self.preorder(node.right)
    
    def inorder(self, node):
        if node.left:
            self.inorder(node.left)
            
        print(" {}".format(node.key), end = "")
        
        if node.right:
            self.inorder(node.right)
            
    def out(self):
        self.inorder(self.root)
        print('')
        self.preorder(self.root)
        print('')

tree = Tree()
N = int(input())
for _ in range(N):
    order = input().split()
    if order[0] == 'insert':
        tree.insert(int(order[1]))
    elif order[0] == 'find':
        print('yes' if tree.find(int(order[1])) else 'no')
    elif order[0] == 'delete':
        tree.delete(int(order[1]))
    else:
        tree.out()

Solution (Python):
m = int(input())

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


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

    def getRoot(self):
        return self.root
    def setRoot(self, v):
        self.root = v

    def inorder(self, v=None):
        if v is None:
            v = self.root
        if v.left is not None:
            self.inorder(v.left)
        print(' ' + str(v.key), end='')
        if v.right is not None:
            self.inorder(v.right)
        
    def preorder(self, v=None):
        if v is None:
            v = self.root
        print(' ' + str(v.key), end='')
        if v.left is not None:
            self.preorder(v.left)
        if v.right is not None:
            self.preorder(v.right)

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

def find(T, k, noprint=False):
    x = T.getRoot()
    while x is not None:
        if x.key == k:
            if not noprint:
                print('yes')
            return x
        elif x.key < k:
            x = x.right
        else:
            x = x.left
    print('no')

def getNext(v):
    if v.right is not None:
        return getMinimum(v.right)  
    y = v.p
    while y is not None and v == y.right:
        v = y
        y = y.p
    return y

def getMinimum(v):
    while v.left is not None:
        v = v.left
    return v


    
def delete(T, z):
    if not z.left and not z.right:
        p = z.p
        if z.key < p.key:
            p.left = None
        else:
            p.right = None

    elif z.left and not z.right:
        p = z.p
        c = z.left
        if z.key > p.key:
            p.right = c
        else:
            p.left = c
        c.p = p
    elif not z.left and z.right:
        p = z.p
        c = z.right
        if z.key > p.key:
            p.right = c
        else:
            p.left = c
        c.p = p
    else:
        n = getNext(z)
        z.key = n.key
        delete(T, n)

T = BinaryTree()

for i in range(m):
    inp = input().split()
    if inp[0] == 'print':
        T.inorder()
        print()
        T.preorder()
        print()
    elif inp[0] == 'find':
        find(T, int(inp[1]))
    elif inp[0] == 'delete':
        delete(T, find(T, int(inp[1]),True))
    else:
        v = Node(int(inp[1]), None, None)
        insert(T, v)

Solution (Python):
class Node():
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.parent = 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_preorder(self, node):
        node_list = []

        node_list.append(node.key)
        if node.left:
            node_list.extend(self.show_preorder(node.left))
        if node.right:
            node_list.extend(self.show_preorder(node.right))

        return node_list

    def show_inorder(self, node):
        node_list = []

        if node.left:
            node_list.extend(self.show_inorder(node.left))
        node_list.append(node.key)
        if node.right:
            node_list.extend(self.show_inorder(node.right))

        return node_list

    def print(self):
        print(' ' + ' '.join(map(str, self.show_inorder(self.root))))
        print(' ' + ' '.join(map(str, self.show_preorder(self.root))))


if __name__ == '__main__':
    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':
            print('yes' if tree.find(int(command[1])) else 'no')
        elif command[0] == 'delete':
            tree.delete(int(command[1]))
        elif command[0] == 'print':
            tree.print()

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

    def insert(self, insert_node):
        p = None
        r = self.root
        while r:
            p = r
            if insert_node.value < r.value:
                r = r.left
            else:
                r = r.right

        if not p:
            self.root = insert_node
        elif insert_node.value < p.value:
            p.left = insert_node
        else:
            p.right = insert_node

    def find(self, find_value):
        r = self.root
        while r:
            if find_value == r.value:
                return "yes"
            if find_value < r.value:
                r = r.left
            else:
                r = r.right
        return "no"

    def delete(self, delete_value):
        flag = None
        p = None
        r = self.root
        while True:
            if delete_value == r.value:
                if r.left == None and r.right == None:
                    if flag == "l":
                        p.left = None
                    else:
                        p.right = None
                    return
                elif r.left == None:
                    if flag == "l":
                        p.left = r.right
                    else:
                        p.right = r.right
                    return
                elif r.right == None:
                    if flag == "l":
                        p.left = r.left
                    else:
                        p.right = r.left
                    return
                else:
                    r2 = r.right
                    while r2:
                        p = r2
                        r2 = r2.left
                    swap_value = p.value
                    self.delete(swap_value)
                    r.value = swap_value
                    return
            elif delete_value < r.value:
                p = r
                r = r.left
                flag = "l"
            else:
                p = r
                r = r.right
                flag = "r"

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

    def pre_order_search(self):
        l = self.left
        r = self.right
        print("",self.value, end="")
        if l:
            l.pre_order_search()
        if r:
            r.pre_order_search()

    def in_order_search(self):
        l = self.left
        r = self.right
        if l:
            l.in_order_search()
        print("",self.value, end="")
        if r:
            r.in_order_search()

m = int(input())
tree = BinaryTree()

for i in range(m):
    inp = input().split()
    if inp[0] == "insert":
        tree.insert(Node(int(inp[1]), None, None))
    elif inp[0] == "find":
        print(tree.find(int(inp[1])))
    elif inp[0] == "delete":
        tree.delete(int(inp[1]))
    else:
        tree.root.in_order_search()
        print()
        tree.root.pre_order_search()
        print()

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

    def insert(self, insert_node):
        p = None
        r = self.root
        while r:
            p = r
            if insert_node.value < r.value:
                r = r.left
            else:
                r = r.right

        if not p:
            self.root = insert_node
        elif insert_node.value < p.value:
            p.left = insert_node
        else:
            p.right = insert_node

    def find(self, find_value):
        r = self.root
        while r:
            if find_value == r.value:
                return "yes"
            if find_value < r.value:
                r = r.left
            else:
                r = r.right
        return "no"

    def delete(self, delete_value):
        flag = None
        p = None
        r = self.root
        while True:
            if delete_value == r.value:
                if r.left == None and r.right == None:
                    if flag == "l":
                        p.left = None
                    else:
                        p.right = None
                    return
                elif r.left == None:
                    if flag == "l":
                        p.left = r.right
                    else:
                        p.right = r.right
                    return
                elif r.right == None:
                    if flag == "l":
                        p.left = r.left
                    else:
                        p.right = r.left
                    return
                else:
                    min_node = r.right
                    while min_node:
                        p = min_node
                        min_node = min_node.left
                    swap_value = p.value
                    self.delete(swap_value)
                    r.value = swap_value
                    return
            elif delete_value < r.value:
                p = r
                r = r.left
                flag = "l"
            else:
                p = r
                r = r.right
                flag = "r"

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

    def pre_order_search(self):
        l = self.left
        r = self.right
        print("",self.value, end="")
        if l:
            l.pre_order_search()
        if r:
            r.pre_order_search()

    def in_order_search(self):
        l = self.left
        r = self.right
        if l:
            l.in_order_search()
        print("",self.value, end="")
        if r:
            r.in_order_search()

m = int(input())
tree = BinaryTree()

for i in range(m):
    inp = input().split()
    if inp[0] == "insert":
        tree.insert(Node(int(inp[1]), None, None))
    elif inp[0] == "find":
        print(tree.find(int(inp[1])))
    elif inp[0] == "delete":
        tree.delete(int(inp[1]))
    else:
        tree.root.in_order_search()
        print()
        tree.root.pre_order_search()
        print()