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.



Sample input:
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:
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

Submission status: Runtime Error

Solution code:
#BinarySearchTree
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 != None:
           key = key.left
        return key
    
    def delete(self, key):
        currentNode = self.find(key)
        
        if currentNode.left == None or currentNode.right == None:
            z = currentNode
        else:
            z = self.next(z)
        
        if z.left != None:
            z.left.parent = z.parent
            if z.parent.key > z.left.key:
                z.parent.left = z.left
            else:
                z.parent.right = z.left
        if z.right != None:
            z.right.parent = z.parent
            if z.parent.key > z.right.key:
                z.parent.left = z.right
            else:
                z.parent.right = z.right
        if z.right == None and z.left == None:
            if z.parent.key > z.key:
                z.parent.left = None
            else:
                z.parent.right = None
        if z != currentNode:
            currentNode = z 

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)
    elif L[0] =="print":
        Tree.show()
    elif L[0] =="find":
        if Tree.find(int(L[1])) == False:
            print("no")
        else:
            print("yes")
    else:
        Tree.delete(int(L[1]))

Submission status: Runtime Error

Solution code:
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:
            return node
        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:
            return Node.delete_min(node.left)
                
        
    def inorder_print(node):
        if node.left != None:
            Node.inorder_print(node.left)
        print("",node.data,  end="")
        if node.right != None:
            Node.inorder_print(node.right)
    def preorder_print(node):
        print("",node.data,  end="")
        if node.left != None:
            Node.preorder_print(node.left)
        if node.right != None:
            Node.preorder_print(node.right)
        
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):
        Node.inorder_print(self.root)
        print()
        Node.preorder_print(self.root)
        print()

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()

Submission status: Runtime Error

Solution code:
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.rightt 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
            while y.left is not None:
                y = y.left

            x.key = y.key
            if y.right is not None:
                y.right.parent = y.parent
                y.parent.left  = y.right
            else:
                y.parent.left = 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()

Submission status: Runtime Error

Solution code:

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:
#        print("parent:{}".format(parent.key))
        if parent.left == old:
            parent.left = new
        else:
            parent.right = new
        if new != None:
            new.p = parent

def delete(node):
    if node == None:
        return
#    print("delete key:{}".format(node.key))
    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(ino):
            if ino[i].key == value:
                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(Tree, root, z):
    y = None # x ??????
    x = root  # 'T ??????'
    while x != None:
        y = x # ???????¨????
        if z.key < x.key:
            x = x.left # ?????????????§????
        else:
            x = x.right # ?????????????§????
    z.p = y

    Tree.append(z)
    if y == None: # T ???????????´???
        return z
    elif z.key < y.key:
        y.left = z # z ??? y ?????????????????????
    else:
        y.right = z # z ??? y ?????????????????????
    return root

def main():

    """ ????????? """
    num = int(input().strip())
    istr = sys.stdin.read()
    cmds = list(istr.splitlines())
    Tree = []
    root = None
    for i in range(num):
        cmd = cmds[i][0]
        if cmd == "i":
            n = Node(int(cmds[i][7:]))
            root = insert(Tree, 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()

Submission status: Runtime Error

Solution code:
class Node():
    def __init__(self, id, left=-1, right=-1, parent=-1, type=None):
        self.id = id
        self.left = left
        self.right = right
        self.parent = parent
        
    def show(self):
        print 'node %d: parent = %d, left = %d, right = %d' % (self.id, self.parent, self.left, self.right)

class Stack():
    def __init__(self):
        self.el = []
    def add(self, el):
        self.el.append(el)
    def pop(self):
        return self.el.pop()

def printOrder(T):
    global rootId
    ### inorder ###
    pos = rootId
    st = Stack()
    ans = []
    while True:
        if T[pos].left != -1 and T[pos].left not in ans:
            if T[pos].right != -1:
                st.add(T[pos].right)
            st.add(pos)
            pos = T[pos].left
        elif T[pos].left == -1 and T[pos].right != -1 and T[pos].right not in ans:
            ans.append(pos)
            pos = T[pos].right
        else:
            ans.append(pos)
            if len(ans) == len(T):
                break
            pos = st.pop()
    print '', ' '.join(map(str, ans))
    ### preorder ###
    pos = rootId
    st = Stack()
    ans = []
    while True:
        ans.append(pos)
        if len(ans) == len(T):
            break
        if T[pos].left != -1 and T[pos].right != -1:
            st.add(T[pos].right)
        if T[pos].left != -1:
            pos = T[pos].left
        elif T[pos].left == -1 and T[pos].right != -1:
            pos = T[pos].right
        else:
            pos = st.pop()
    print '', ' '.join(map(str, ans))

def insert(T, z):
    global rootId
    y = None
    if rootId:
        x = T[rootId]
        while x != None:
            y = x
            if z.id < x.id:
                if x.left == -1:
                    break
                x = T[x.left]
            else:
                if x.right == -1:
                    break
                x = T[x.right]
        z.parent = x.id
    if y == None:
        rootId = z.id
    elif z.id < y.id:
        y.left = z.id
    else:
        y.right = z.id
    T[z.id] = z
    return T

def find(T, z):
    global rootId
    y = None
    if rootId:
        x = T[rootId]
        while True:
            y = x
            if z == x.id:
                print 'yes'
                break
            elif z < x.id:
                if x.left == -1:
                    print 'no'
                    break
                x = T[x.left]
            else:
                if x.right == -1:
                    print 'no'
                    break
                x = T[x.right]

def delete(T, z):
    global rootId
    y = None
    if rootId:
        x = T[rootId]
        while True:
            y = x
            if z == x.id:
                if x.right != -1:
                    T[x.right].parent = x.parent
                elif x.left != -1:
                    T[x.left].parent = x.parent
                if T[x.parent].right == z:
                    T[x.parent].right = x.right
                else:
                    T[x.parent].left = x.left
                break
            elif z < x.id:
                if x.left == -1:
                    break
                x = T[x.left]
            else:
                if x.right == -1:
                    break
                x = T[x.right]
    del T[z]
    return T

### input ###
T = {}
a = []
n = int(raw_input())
rootId = None
for i in range(n):
    tmp = raw_input().split()
    if tmp[0] == 'insert':
        T[int(tmp[1])] = Node(int(tmp[1]))
        T = insert(T, Node(int(tmp[1])))
    elif tmp[0] == 'find':
        find(T, int(tmp[1]))
    elif tmp[0] == 'delete':
        T = delete(T, int(tmp[1]))
    elif tmp[0] == 'print':
        printOrder(T)

Submission status: Runtime Error

Solution code:
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.left is not None:
        return v.left
    if v.right is not None:
        return v.right    

    
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)

Submission status: Runtime Error

Solution code:
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 == 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:
                    swap_value = search_min(r.right)
                    self.delete(swap_value)
                    r.value = swap_value
            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()

    def search_min(self):
        l = self.left
        while l:
            search_min(l)
        return self.value

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()

Submission status: Runtime Error

Solution code:
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 == 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
            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()

Submission status: Runtime Error

Solution code:


class Node(object):

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

        self.key = key


class Tree(object):

    def __init__(self):
        self.root = None

    def insert(self, new_key):
        x = self.root
        y = None

        while x is not None:
            y = x

            if new_key < y.key:
                x = y.left
            else:
                x = y.right

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

    def inorder(self, now):
        visited = list()
        if now is None:
            return visited

        visited.extend(self.inorder(now.left))
        visited.append(now.key)
        visited.extend(self.inorder(now.right))
        return visited

    def preorder(self, now):
        visited = list()
        if now is None:
            return visited

        visited.append(now.key)
        visited.extend(self.preorder(now.left))
        visited.extend(self.preorder(now.right))
        return visited

    def order_print(self):
        keys = list()
        keys.append(self.inorder(self.root))
        keys.append(self.preorder(self.root))

        for visited_keys in keys:
            print "",
            print " ".join(map(str, visited_keys))

    def find(self, key):
        """
        keys = self.inorder(self.root)
        if key in keys:
            print "yes"
        else:
            print "no"
        """
        x = self.root
        y = None

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

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


    def min_node(self, now):
        """min_node
        Return the node with the minimum key,
        treeting now as the root of a sub tree.
        """
        if now.left is not None:
            return min_node(now.left)
        return now


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

        while x.key != key:
            y = x
            if key < y.key:
                x = y.left
            else:
                x = y.right

        # y is parent of x here
        if x.left is None and x.right is None:
            if y.left == x:
                y.left = None
            else:
                y.right = None
        elif x.left is None or x.right is None:
            child = x.left if x.left is not None else x.right
            child.parent = y
            if y.left == x:
                y.left = child
            else:
                y.right = child
        else:
            next_node = self.min_node(x.right)
            x.key = next_node.key
            self.delete(next_node)


def main():
    tree = Tree()

    num_orders = int(raw_input())
    for _ in xrange(num_orders):
        order = raw_input()
        if order[0] == 'i':
            new_key = int(order.split()[1])
            tree.insert(new_key)
        elif order[0] == 'p':
            tree.order_print()
        elif order[0] == 'f':
            key = int(order.split()[1])
            tree.find(key)
        elif order[0] == 'd':
            key = int(order.split()[1])
            tree.delete(key)


if __name__ == "__main__":
    main()