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:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_8_A&lang=jp
# cat alds1_8_c.txt | ./alds1_8_c.py

import sys


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


def insert(key, node):
    """
    ??????????????????????????????, ???????????°???????????? node.left ????????? node.right ?????????????????????
    """
    if key < node.key:
        if node.left is None:
            left_node = Node(key, node)
            node.left = left_node
        else:
            insert(key, node.left)
    else:
        if node.right is None:
            right_node = Node(key, node)
            node.right = right_node
        else:
            insert(key, node.right)


def find(key, node):
    """
    ??????????????????????????????, ?????????????????¨????????°?????????????????????????????´?????????
    ????????????????????§??????????????????????????????????????¨??????????????° None ????????????
    """
    if key == node.key:
        return node
    elif key < node.key:
        if node.left is None:
            return None
        else:
            return find(key, node.left)
    else:
        if node.right is None:
            return None
        else:
            return find(key, node.right)


def print_preorder(node):
    print(" %d" % node.key, end="")
    if node.left is not None:
        print_preorder(node.left)
    if node.right is not None:
        print_preorder(node.right)


def print_inorder(node):
    if node.left is not None:
        print_inorder(node.left)
    print(" %d" % node.key, end="")
    if node.right is not None:
        print_inorder(node.right)


def search_minimum_node(node):
    """
    node ???????????¨??????(??¨???)??¨??????????°????????????????????????????????????????
    ?????? node ??????????????±????????´??? leaf ?????¢?´¢??????????????§?????????
    """
    if node.left is not None:
        return search_minimum_node(node.left)
    else:
        return node


def delete(node):
    if node.left is None and node.right is None:
        # ?????? node ??????????????§, ?????? parent ???????????§??§????????????????????????
        if node.parent.left is node:
            node.parent.left = None
        else:
            node.parent.right = None
    elif node.left is None and node.right is not None:
        # node ??????????????????????????§, node ????????? node ????????????????????§?????????????????????
        # node ??????????????? node ???????????????????????¨???????????§?????????????????????
        if node is node.parent.left:
            # node ?????????????????????
            node.parent.left = node.right
        else:
            # node ?????????????????????
            node.parent.right = node.right
        node.right.parent = node.parent
    elif node.left is not None and node.right is None:
        # node ??????????????????????????§, node ????????? node ????????????????????§?????????????????????
        # node ??????????????? node ???????????????????????¨???????????§?????????????????????
        if node is node.parent.left:
            # node ?????????????????????
            node.parent.left = node.left
        else:
            # node ?????????????????????
            node.parent.right = node.left
        node.leftt.parent = node.parent
    else:
        # ????????????????????????????????????
        # ?¬??????? (successor) ????¨??????????
        successor = search_minimum_node(node.right)
        if successor.right is not None:
            # ??????????¬???????????????´??? node ???????????´???, ?????????????????????????????????
            successor.right.parent = successor.parent
            successor.parent.left = successor.right
        else:
            # ?¬???????????????´??? node ???????????´???, ?¬????????????????????????????????????????
            successor.parent.right = None
        # node ??????????¬???????????????§???????????????
        node.key = successor.key


def main():
    lines = sys.stdin.readlines()
    root = Node()

    for order in lines[1:]:
        if order.startswith("insert"):
            _, key = order.strip().split(" ")
            key = int(key)
            if root.key is None:
                root.key = key
            else:
                insert(key, root)
        elif order.startswith("find"):
            _, key = order.strip().split(" ")
            fild_result = "no" if find(int(key), root) is None else "yes"
            print(fild_result)
        elif order.startswith("print"):
            print_inorder(root)
            print("")
            print_preorder(root)
            print("")
        elif order.startswith("delete"):
            _, key = order.strip().split(" ")
            node = find(int(key), root)  # ????????§ node ???????????????????????£?????¨???????????????????§???§????????????
            delete(node)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from __future__ import print_function
from sys import stdin
class Node:
    def __init__(self, id):
        self.id = id
        self.left = None
        self.right = None
        self.parent = None

def preorder_tree_walk(root):
    print('', root.id, end='')
    if root.left != None:
        preorder_tree_walk(root.left)
    if root.right != None:
        preorder_tree_walk(root.right)

def inorder_tree_walk(root):
    if root.left != None:
        inorder_tree_walk(root.left)
    print('', root.id, end='')
    if root.right != None:
        inorder_tree_walk(root.right)

def insert(root, z):
    y = None
    x = root
    while isinstance(x, Node):
        y = x
        if z.id < x.id:
            x = x.left
        else:
            x = x.right
    z.parent = y

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

def find(root, x):
    while root != None and x != root.id:
        if x < root.id:
            root = root.left
        else:
            root = root.right
    return root

def delete(root, z):
    # detect delete node y.
    if  z.left == None or z.right == None:
        y = z
    else:
        y = get_successor(z)

    # detect y's child x
    if y.left != None:
        x = y.left
    else:
        x = y.right

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

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

    if y != z:
        z.id = y.id


def get_successor(x):
    if x.right != None:
        return get_minimum(x.right)

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

def get_minumum(x):
    while x.left != None:
        x = x.left
    return x


n = int(raw_input())
root = None
for i in xrange(n):
    cmd = stdin.readline()
    if cmd.startswith('i'):
        num = int(cmd[7:])
        root = insert(root, Node(num))
    elif cmd.startswith('p'):
        inorder_tree_walk(root)
        print()
        preorder_tree_walk(root)
        print()
    elif cmd.startswith('d'):
        num = int(cmd[7:])
        node = find(root, num)
        if node != None:
            delete(root, node)
    else:
        # find
        num = int(cmd[5:])
        if find(root, num) != None:
            print('yes')
        else:
            print('no')

Submission status: Runtime Error

Solution code:
def insert(tree,k):
    y = None
    x = tree
    z = {'key':k, 'parent':None, 'left':None, 'right':None}
    while x != None:
        y = x
        if x['key'] > k:
            x = x['left']
        else:
            x = x['right']
    z['parent'] = y
    if y == None:
        tree = z
    elif y['key'] > k:
        y['left'] = z
    else:
        y['right'] = z
    return tree

def delete_leaf(p,x):
    if left(p,x):
        p['left'] = None
    else:
        p['right'] = None
    return p

def delete_half_leaf(p,x,y):
    if left(p,x):
        p['left'] = y
    else:
        p['right'] = y
    y['parent'] = p
    return p


def left(p,x):
    if p['left'] != None and p['left']['key'] == x['key']:
        return True
    else:
        return False

def delete_internal(p,x):
    y = x['right']
    while y['left'] != None:
        y = y['left']
    x['key'] = y['key']
    if y['right'] == None:
        tree = delete_leaf(tree,y['parent'],y)
    else:
        tree = delete_half_leaf(tree,y['parent'],y,y['left'])
    return p

def delete(tree,k):
    x = find(tree,k)
    if x == None: return
    p = x['parent']
    if p == None:
        pass
    else:
        if x['left'] == x['right'] == None:
            p = delete_leaf(p,x)
        elif x['right'] == None:
            p = delete_half_leaf(p,x,x['left'])
        elif x['left'] == None:
            p = delete_half_leaf(p,x,x['right'])
        else:
            p = delete_internal(p,x)
    return tree

def find(tree,k):
    x = tree
    while x != None:
        if x['key'] == k:
            return x
        elif x['key'] > k:
            x = x['left']
        else:
            x = x['right']
    return None

def middleorder(x):
    if x != None:
        middleorder(x['left'])
        print x['key'],
        middleorder(x['right'])

def preorder(x):
    if x != None:
        print x['key'],
        preorder(x['left'])
        preorder(x['right'])



tree = None
m = int(raw_input())
for i in range(m):
    c = raw_input().strip()
    if c[0] == 'i':
        tree = insert(tree, int(c[7:]))
    elif c[0] == 'f':
        x = find(tree, int(c[5:]))
        if x == None:
            print "no"
        else:
            print "yes"
    elif c[0] == 'd':
        tree = delete(tree, int(c[7:]))
    elif c[0] == 'p':
        print '',
        middleorder(tree)
        print
        print '',
        preorder(tree)
        print

Submission status: Runtime Error

Solution code:
def insert(tree,k):
    y = None
    x = tree
    z = {'key':k, 'parent':None, 'left':None, 'right':None}
    while x != None:
        y = x
        if x['key'] > k:
            x = x['left']
        else:
            x = x['right']
    z['parent'] = y
    if y == None:
        tree = z
    elif y['key'] > k:
        y['left'] = z
    else:
        y['right'] = z
    return tree

def get_successor(x):
    if x['right'] != None:
        return get_minimum(x['right'])
    else:
        y = x['parent']
        while y != None and x == y['left']:
            x = y
            y = y['parent']
        return y

def get_minimum(x):
    while x['left'] != None:
        x = x['left']
    return x

def delete_node(tree,z):
    if z['left'] == None or z['right'] == None:
        y = z
    else:
        y = get_successor(z)

    if y['left'] != None:
        x = y['left']
    else:
        x = y['right']

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

    if y['parent'] == None:
        tree = x
    else:
        if y['parent']['left']['key'] == y['key']:
            y['parent']['left'] = x
        else:
            y['parent']['right'] = x

    z['key'] = y['key']

    return tree

def find(tree,k):
    x = tree
    while x != None:
        if x['key'] == k:
            return x
        elif x['key'] > k:
            x = x['left']
        else:
            x = x['right']
    return None

def middleorder(x):
    if x != None:
        middleorder(x['left'])
        print x['key'],
        middleorder(x['right'])

def preorder(x):
    if x != None:
        print x['key'],
        preorder(x['left'])
        preorder(x['right'])



tree = None
m = int(raw_input())
for i in range(m):
    c = raw_input().strip()
    if c[0] == 'i':
        tree = insert(tree, int(c[7:]))
    elif c[0] == 'f':
        x = find(tree, int(c[5:]))
        if x == None:
            print "no"
        else:
            print "yes"
    elif c[0] == 'd':
        z = find(tree, int(c[7:]))
        if not z == None: tree = delete_node(tree,z)
    elif c[0] == 'p':
        print '',
        middleorder(tree)
        print
        print '',
        preorder(tree)
        print

Submission status: Runtime Error

Solution code:
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
        node.parent = y

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

    def find_node(self, value):
        return self.root.find(value)

    def find(self, value):
        print('yes' if self.find_node(value) else 'no')

    def delete(self, value):
        self.find_node(value).delete()

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


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

    def find(self, value):
        diff = self.key - value
        if diff == 0:
            return self
        elif diff > 0:
            return self.left and self.left.find(value)
        else:
            return self.right and self.right.find(value)

    def delete(self):
        if self.left:
            self.delete_connect(self.parent, self.left)
        elif self.right:
            self.delete_connect(self.parent, self.right)
        else:
            self.delete_connect(self.parent, None)

    def delete_connect(self, parent, child):
        if parent:
            if parent.key > self.key:
                parent.left = child
            else:
                parent.right = child
        if child:
            child.parent = parent

    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()
    f = l[0]
    if f == 'i':
        tree.insert(Node(int(l.split()[1])))
    elif f == 'f':
        tree.find(int(l.split()[1]))
    elif f == 'd':
        tree.delete(int(l.split()[1]))
    else:
        tree.print()
    m -= 1

Submission status: Runtime Error

Solution code:
class BinarySearchTree:
    root = None
    def insert(self, k):
        y = None
        x = self.root
        z = Node(k)
        while x:
            y = x
            if z.k < x.k:
                x = x.l
            else:
                x = x.r
        z.p = y
         
        if y == None:
            self.root = z
        else:
            if z.k < y.k:
                y.l = z
            else:
                y.r = z
                
    def find(self, x, k):
        while x != None and k != x.k:
            if k < x.k:
                x = x.l
            else:
                x = x.r
        return x
     
    def deleteNode(self, z):
        y = None
        x = None
        if z.l == None or x.r == None:
            y = z
        else:
            y = self.getSuccessor(z)
        
        if y.l != None:
            x = y.l
        else:
            x = y.r
        
        if x != None:
            x.p = y.p
        
        if y.p == None:
            self.root = x
        else:
            if y == y.p.l:
                y.p.l = x
            else:
                y.p.r = x
        
        if y != z:
            z.k = y.k

    def getSuccessor(self, x):
        if x.r != None:
            return self.getMinimum(x.r)
        y = x.p
        while y != None and x == y.r:
            x = y
            y = y.p
        return y
    
    def getMinimum(self, x):
        while x.l != None:
            x = x.l
        return x
    
    def preParse(self, u):
        if u == None:
            return
        print("", str(u.k), end = "")
        self.preParse(u.l)
        self.preParse(u.r)
 
    def inParse(self, u):
        if u == None:
            return
        self.inParse(u.l)
        print("", str(u.k), end = "")
        self.inParse(u.r)
 
class Node: 
    def __init__(self, k):
        self.k = k
        self.p = None
        self.l = None
        self.r = None
 
if __name__ == '__main__':
    n = int(input().rstrip())
    x = BinarySearchTree()
    for i in range(n):
        com = input().rstrip()
        if com.startswith("insert"):
            k = int(com.split(" ")[1])
            x.insert(k)
        elif com.startswith("find"):
            k = int(com.split(" ")[1])
            if x.find(x.root, k) != None:
                print("yes")
            else:
                print("no")
        elif com.startswith("delete"):
            k = int(com.split(" ")[1])
            x.deleteNode(x.find(x.root, k))
        else:
            x.inParse(x.root)
            print()
            x.preParse(x.root)
            print()

Submission status: Runtime Error

Solution code:
import sys
import os

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        
    def insert_node(self, node):
        if node.value <= self.value:
            if self.left is None:
                self.left = node
            else:
                self.left.insert_node(node)
        else:
            if self.right is None:
                self.right = node
            else:
                self.right.insert_node(node)

    def find_node_by_value(self, value):
        if self.value == value:
            return self
        elif value < self.value:
            if self.left is None:
                return None
            else:
                return self.left.find_node_by_value(value)
        elif value > self.value:
            if self.right is None:
                return None
            else:
                return self.right.find_node_by_value(value)
        else:
            assert(False)   

    def next_node_in_inorder(self):
        if self.right is not None:
            return self.right.smallest_offspring(self)
        else:
            return None

    def smallest_offspring(self, parent):
        if self.left is not None:
            return smallest_offspring(self.left, self)
        else:
            return (self, parent)

    def get_parent_of(self, value, parent_cand=None, is_left_child=None):
        if self.value == value:
            return parent_cand, is_left_child
        else:
            if value < self.value and self.left is not None:
                return self.left.get_parent_of(value, self, True)
            elif value > self.value and self.right is not None:
                return self.right.get_parent_of(value, self, False)
            else:
                assert(False)

    def delete_child(self, node):
        if self.left == node:
            self.left = None
        elif self.right == node:
            self.right = None
        else:
            assert(False)
            
    def delete_node(self, parent, value):
        # recursive
        if value < self.value and self.left is not None:
            self.left.delete_node(self, value)
        elif self.value < value and self.right is not None:
            self.right.delete_node(self, value)
        # delete
        elif self.left is None and self.right is None:
            # no children
            parent.delete_child(self)
        elif self.left is not None and self.right is not None:
            n, p = self.next_node_in_inorder()
            self.value = n.value
            n.delete_node(p, n.value)
        elif self.left is not None:
            self.value = self.left.value
            self.right = self.left.right
            self.left = self.left.left
        elif self.right is not None:
            self.value = self.right.value
            self.left = self.right.left
            self.right = self.right.right
    
#     def delete_node_by_value(self, value):
#         node = self.find_node_by_value(value)
#         parent, node_is_left_child = self.get_parent_of(value)
#         if node.left is None and node.right is None:
#             # hard delete
#             if parent is not None:
#                 if node_is_left_child:
#                     parent.left = None
#                 else:
#                     parent.right = None
#             else:
#                 return 'DELETE_BST'
#         else:
#         self.forcedelete(node, parent, node_is_left_child)

                
    def print_node_by_preorder(self):
        print('', self.value, end='')
        if self.left is not None:
            self.left.print_node_by_preorder()
        if self.right is not None:
            self.right.print_node_by_preorder()


    def print_node_by_inorder(self):
        if self.left is not None:
            self.left.print_node_by_inorder()
        print('', self.value, end='')
        if self.right is not None:
            self.right.print_node_by_inorder()

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

    def cmd_insert(self, k):
        if self.root is None:
            self.root = Node(k)
        else:
            self.root.insert_node(Node(k))

    def cmd_find(self, k):
        if self.root is None:
            return False
        else:
            return (self.root.find_node_by_value(k) is not None)

    def cmd_delete(self, k):
        if self.root is None:
            pass
        else:
            self.root.delete_node(parent=self, value=k)

    def delete_child(self, node):
        assert(self.root == node)
        self.root = None

    def cmd_print(self):
        if self.root is not None:
            self.root.print_node_by_inorder()
            print()
            self.root.print_node_by_preorder()
            print()


if __name__ == '__main__':
    bst = BST()

    lines = []
    for line in sys.stdin:
        lines.append(line.rstrip())
    num_cmds = int(lines[0])
    for line in lines[1:1+num_cmds]:
        line_split = line.split(' ')
        cmd = line_split[0]

        try:
            val = int(line_split[1])
        except:
            pass
        if cmd == 'insert':
            bst.cmd_insert(val)
        elif cmd == 'find':
            if bst.cmd_find(val):
                print('yes')
            else:
                print('no')
        elif cmd == 'print':
            bst.cmd_print()
        elif cmd == 'delete':
            bst.cmd_delete(val)
        else:
            assert(False)

Submission status: Runtime Error

Solution code:
def insert(r, n):
    if 0 == len(T):
        T[n] = [None, None, None]
    else:
        if n < r:
            left = T[r][0]
            if left == None:
                T[r][0] = n
                T[n] = [None, None, r]
            else:
                insert(left, n)
        if r < n:
            right = T[r][1]
            if right == None:
                T[r][1] = n
                T[n] = [None, None, r]
            else:
                insert(right, n)

def find(n):
    if n in T:
        return True
    else:
        return False

def dele(r, n):
    z = T[n]
    left = z[0]
    right = z[1]
    p = z[2]
    if left is None and right is None:
        T[p][1] = None
        del z
    elif left is None and right is not None:
        T[p][1] = right
        T[right][2] = z[2]
        del z
    elif left is not None and right is None:
        T[p][0] = left
        T[left][2] = z[2]
        del z
    elif left is not None and right is not None:
        inorder = list(map(int, print_inorder(r).split()))
        next_n = inorder[inorder.index(n) + 1]
        if r == n:
            r = next_n
        dele(r, next_n)
        T[next_n] = T[n]
        del T[n]
        for k,v in T.items():
            if v[0] == n:
                v[0] = next_n
            if v[1] == n:
                v[1] = next_n
            if v[2] == n:
                v[2] = next_n
    return r

def print_inorder(r):
    left = T[r][0]
    right = T[r][1]
    ans = ""
    if left != None:
        ans += print_inorder(left)
    ans += " {}".format(r)
    if right != None:
        ans += print_inorder(right)
    return ans

def print_preorder(r):
    left = T[r][0]
    right = T[r][1]
    ans = " {}".format(r)
    if left != None:
        ans += print_preorder(left)
    if right != None:
        ans += print_preorder(right)
    return ans

n = int(input())
T = {}

root = None
for i in range(n):
    inst = input()
    if inst[0] == 'i':
        num = int(inst[7:])
        if i == 0:
            root = num
        insert(root, num)
    elif inst[0] == 'f':
        num = int(inst[5:])
        if find(num):
            print("yes")
        else:
            print("no")
    elif inst[0] == 'd':
        num = int(inst[7:])
        root = dele(root, num)
    elif inst[0] == 'p':
        print(print_inorder(root))
        print(print_preorder(root))

Submission status: Runtime Error

Solution code:
def insert(r, n):
    if 0 == len(T):
        T[n] = [None, None, None]
    else:
        if n < r:
            left = T[r][0]
            if left == None:
                T[r][0] = n
                T[n] = [None, None, r]
            else:
                insert(left, n)
        if r < n:
            right = T[r][1]
            if right == None:
                T[r][1] = n
                T[n] = [None, None, r]
            else:
                insert(right, n)

def find(n):
    if n in T:
        return True
    else:
        return False

def dele(r, n):
    if find(n):
        z = T[n]
        left = z[0]
        right = z[1]
        p = z[2]
        if left is None and right is None:
            i = T[p].index(n)
            T[p][i] = None
            del T[n]
        elif left is None and right is not None:
            x = T[p].index(n)
            T[p][x] = right
            T[right][2] = z[2]
            del T[n]
        elif left is not None and right is None:
            x = T[p].index(n)
            T[p][x] = left
            T[left][2] = z[2]
            del T[n]
        elif left is not None and right is not None:
            inorder = list(map(int, print_inorder(r).split()))
            next_n = inorder[inorder.index(n) + 1]
            if r == n:
                r = next_n
            dele(r, next_n)
            T[next_n] = T[n]
            del T[n]
            next_l = T[next_n][0]
            if next_l is not None:
                for i in T[next_l]:
                    if n == i:
                        T[next_l][i] = n
            next_r = T[next_n][1]
            if next_r is not None:
                for i in T[next_r]:
                    if n == i:
                        T[next_r][i] = n
    return r

def print_inorder(r):
    left = T[r][0]
    right = T[r][1]
    ans = ""
    if left != None:
        ans += print_inorder(left)
    ans += " {}".format(r)
    if right != None:
        ans += print_inorder(right)
    return ans

def print_preorder(r):
    left = T[r][0]
    right = T[r][1]
    ans = " {}".format(r)
    if left != None:
        ans += print_preorder(left)
    if right != None:
        ans += print_preorder(right)
    return ans

n = int(input())
T = {}

root = None
for i in range(n):
    inst = input()
    if inst[0] == 'i':
        num = int(inst[7:])
        if i == 0:
            root = num
        insert(root, num)
    elif inst[0] == 'f':
        num = int(inst[5:])
        if find(num):
            print("yes")
        else:
            print("no")
    elif inst[0] == 'd':
        num = int(inst[7:])
        root = dele(root, num)
    elif inst[0] == 'p':
        print(print_inorder(root))
        print(print_preorder(root))