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: Wrong Answer

Solution code:
class Node:
    def __init__(self, key):
        self.key = key
        self.parent = None
        self.left = None
        self.right = None
class Tree:
    def __init__(self):
        self.root = None
        self.inorder = []
        self.preorder = []

    def insert(self, node):

        p = None
        x = self.root        
        while x is not None:
            p = x
            # print(node.key, x.key)
            if node.key <= x.key:
                x = x.left
            else:
                x = x.right

        # insertするnodeの親を設定
        node.parent = p

        if p is None:
            self.root = node
        else:
            # insertするnodeを親のleftかrightに設定
            if node.key <= p.key:
                # print('leftに設定')
                p.left = node
            else:
                # print('rightに設定')
                p.right = node

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

    def delete(self, z):
        # print("delete =========", z.key)
        # print(z.key)
        # print(z.parent)
        p = z.parent
        # print(p.key)

        # 1. zが子を持たない場合
        if z.left is None and z.right is None:
            # print('pattern 1')
            if p.left == z:
                p.left = None
            else:
                p.right = None

        # 3. zが子を2つ持つ場合
        elif z.left is not None and z.right is not None:
            # print('pattern 2')
            next_node = tree.get_next_node(z)
            z.key = next_node.key
            self.delete(next_node)

        # 2. zがちょうど1つの子を持つ場合
        else:
            # print('pattern 3')
            # zが左子だった場合
            if p.left.key == z.key:
                if z.left is not None:
                    p.left = z.left
                    z.left.parent = p
                else:
                    p.left = z.right
                    z.right.parent = p
            else:
                # zが右子だった場合
                if z.left is not None:
                    p.right = z.left
                    z.left.parent = p
                else:
                    p.right = z.right
                    z.right.parent = p

    def get_next_node(self, node):
        if node.right is not None:
            return self.get_minimum(node)
        p = x.parent
        while p is not None and p != p.parent.left:
            p = p.parent
        return p.parent

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

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

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

    def inorder_traverse(self, node):
        if node is None:
            return
        self.inorder_traverse(node.left)
        self.inorder.append(node.key)
        self.inorder_traverse(node.right)

    def preorder_traverse(self, node):
        if node is None:
            return
        self.preorder.append(node.key)
        self.preorder_traverse(node.left)
        self.preorder_traverse(node.right)

tree = Tree()
m = int(input())
for i in range(m):
    line = input().split()
    if line[0] == 'print':
        # print('root', str(tree.root.key))
        tree.print_inorder()
        tree.print_preorder()
    elif line[0] == 'insert':
        key = int(line[1])
        tree.insert(Node(key))
    elif line[0] == 'find':
        key = int(line[1])
        if tree.find(key):
            print('yes')
        else:
            print('no')
    elif line[0] == 'delete':
        
        # print("current tree----")
        # print(tree.root.key)
        # print(tree.root.left.key)
        # print(tree.root.left.right.key)
        # print(tree.root.left.right.parent.key)
        # print("current tree----")
        key = int(line[1])
        # print('delete', str(key))
        node = tree.find(key)
        # print('node.key', node.key)
        tree.delete(node)

Submission status: Wrong Answer

Solution code:
import sys
 
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = self.right = None
    
    def __eq__(self, other):
        return self.val == other.val
 
class BST:
    def __init__(self):
        self.root = None
     
    def insert(self, node):
        def helper(root):
            y, x = None, root
            while isinstance(x, TreeNode):
                y = x
                if node.val < x.val:
                    x = x.left
                else:
                    x = x.right
            if y is None:
                root = node
            elif node.val < y.val:
                y.left = node
            else:
                y.right = node
            return root
             
        self.root = helper(self.root)
 
    def find(self, val):
        def helper(root):
            if root is None:
                return None
            elif root.val == val:
                return root
            elif val < root.val:
                return helper(root.left)
            else:
                return helper(root.right)
        return helper(self.root)
        
    def delete(self, val):
        node = TreeNode(val)
        def findMax(root):
            while root.right is not None:
                root = root.right
            return root
        
        def helper(root, node):
            if root is None:
                return None
            elif root == node:
                if root.left is None:
                    root = root.right
                elif root.right is None:
                    root = root.left
                else:
                    tmp = findMax(root.left)
                    root.val = tmp.val
                    lr = helper(root.left, TreeNode(tmp.val))
                    root.left = lr
                return root
            else:
                if node.val < root.val:
                    root.left = helper(root.left, node)
                else:
                    root.right = helper(root.right, node)
                return root

        helper(self.root, node)
        
    def inorder(self):
        def helper(root):
            return [] if root is None else helper(root.left) + [root.val] + helper(root.right)
        return helper(self.root)
 
    def preorder(self):
        def helper(root):
            return [] if root is None else [root.val] + helper(root.left) + helper(root.right)
        return helper(self.root)
 
if __name__ == '__main__':
    q = sys.stdin.readline()
    q = int(q)
    bst = BST()
    for _ in range(q):
        tmp = sys.stdin.readline()
        if tmp.startswith('print'):
            print ' ' + ' '.join(map(lambda x: str(x), bst.inorder()))
            print ' ' + ' '.join(map(lambda x: str(x), bst.preorder()))
        elif tmp.startswith('insert'):
            _, val = tmp.split()
            node = TreeNode(int(val))
            bst.insert(node)
        elif tmp.startswith('find'):
            _, val = tmp.split()
            print ('yes' if bst.find(int(val)) is not None else 'no')
        else:
            _, val = tmp.split()
            bst.delete(int(val))

Submission status: Wrong Answer

Solution code:
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_8_C
# Binary Search Tree III
# Result:
import sys

class BinarySearchTree(object):
    def __init__(self):
        super(BinarySearchTree, self).__init__()
        self.root = None
        self.count = 0

    def insert(self, val):
        node = Node(val)
        y = None
        x = self.root
        while x != None:
            y = x
            if node.id_ < x.id_:
                x = x.left
            else:
                x = x.right
        node.parent = y

        if y == None:
            self.root = node
        elif node.id_ < y.id_:
            y.left = node
        else:
            y.right = node

    def find(self, val):
        x = self.root
        while x != None:
            if val == x.id_:
                break
            elif val < x.id_:
                x = x.left
            else: # val > x.id_
                x = x.right
        if x != None:
            return True
        else:
            return False

    def delete(self, val):
        p = None
        x = self.root
        while x != None:
            if val == x.id_:
                break
            p = x
            if val < x.id_:
                x = x.left
            else: # val > x.id_
                x = x.right
        if x != None:
            if x.left != None and x.right != None:
                next_ = self._next_node_in_inorder(x)
                x.id_ = next_.id_
                x = next_
                p = next_.parent
            if x.left == None and x.right == None:
                if p.left == x:
                    p.left = None
                else: #p.right == x
                    p.right = None
            elif x.left == None: # x.right != None
                x.right.parent = p
                p.right = x.right
            elif x.right == None: # x.left != None
                x.left.parent = p
                p.left = x.left

    def _next_node_in_inorder(self, node):
        x = node.right
        while x.left != None:
            x = x.left
        return x

    def __str__(self):
        return 'Call to_inorder_walk() or to_preorder_walk()'

    def to_inorder_walk(self):
        return self._to_inorder_walk(self.root)

    def to_preorder_walk(self):
        return self._to_preorder_walk(self.root)

    def _to_inorder_walk(self, node):
        if node == None: return ''
        str_ = self._to_inorder_walk(node.left)
        str_ += ' %d' % (node.id_)
        str_ += self._to_inorder_walk(node.right)
        return str_

    def _to_preorder_walk(self, node):
        if node == None: return ''
        str_ = ' %d' % (node.id_)
        str_ += self._to_preorder_walk(node.left)
        str_ += self._to_preorder_walk(node.right)
        return str_

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

    def __str__(self):
        str_ = '%d' % (self.id_)
        return str_


bst = BinarySearchTree()

_nops = int(sys.stdin.readline())
for _ in range(0, _nops):
    op = sys.stdin.readline().rstrip().split(' ')
    if op[0] == 'insert':
        bst.insert(int(op[1]))
    elif op[0] == 'print':
        print bst.to_inorder_walk()
        print bst.to_preorder_walk()
    elif op[0] == 'find':
        if bst.find(int(op[1])):
            print 'yes'
        else:
            print 'no'
    elif op[0] == 'delete':
        bst.delete(int(op[1]))
    else:
        pass

Submission status: Wrong Answer

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.left = 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: Wrong Answer

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.left.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: Wrong Answer

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.paremt = 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: Wrong Answer

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

def insert(T,z):
    x=T
    y=None
    while isinstance(x,node):
        y=x
        if z.key<x.key:
            x=x.left
        else:
            x=x.right
    z.parent=y
    if y is None:
        T=z
    elif z.key<y.key:
        y.left=z
    else:
        y.right=z
    return T

def find(T,z):
    if T is None:
        return False
    else:
        y=None
        x=T
        while 1:
            y=x
            if x is None:
                return False
            elif z.key==x.key:
                return True
            elif z.key<x.key:
                x=x.left
            else:
                x=x.right
                
def delete(T,z,i):
    if i==0:
        x=T
        y=None
        while 1:    
            y=x
            if x is None:
                return 
            elif z.key==x.key:
                break
            elif z.key<x.key:
                x=x.left
            else:
                x=x.right
            z.parent=y
        z=x     
    if z.left is None and z.right is None:
        if z is z.parent.right:
            z.parent.right=None
        else:
            z.parent.left=None
    elif z.left is None:
        if z is z.parent.left:
            z.parent.left=z.right
            z.right.parent=z.parent
        else:
            z.parent.right=z.right
            z.right.parent=z.parent
    elif z.right is None:
        if z is z.parent.left:
            z.parent.left=z.left
            z.left.parent=z.parent
        else:
            z.parent.right=z.left
            z.left.parent=z.parent
    else:
        y=z.right
        z.key=y.key
        delete(T,y,1)
           
def preorder(u):
    if u is None:
        return
    pripre.append(str(u.key))
    preorder(u.left)
    preorder(u.right)

def inorder(u):
    if u is None:
        return
    inorder(u.left)
    priin.append(str(u.key))
    inorder(u.right)

m=input()
root=None
for i in xrange(m):
    cmd=map(str,raw_input().split())
    if cmd[0]=="print":
        pripre=[]
        priin=[]
        preorder(root)
        inorder(root)
        print(' '+' '.join(priin))
        print(' '+' '.join(pripre))
    elif cmd[0]=="find":
        key=int(cmd[1])
        z=node(key)
        if find(root,z):
            print('yes')
        else:
            print('no')
    elif cmd[0]=='delete':
        key=int(cmd[1])
        z=node(key)
        delete(root,z,0)
    else:
        key=int(cmd[1])
        z=node(key)
        root=insert(root,z)

Submission status: Wrong Answer

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

def insert(T,z):
    x=T
    y=None
    while isinstance(x,node):
        y=x
        if z.key<x.key:
            x=x.left
        else:
            x=x.right
    z.parent=y
    if y is None:
        T=z
    elif z.key<y.key:
        y.left=z
    else:
        y.right=z
    return T

def find(T,z):
    if T is None:
        return False
    else:
        y=None
        x=T
        while 1:
            y=x
            if x is None:
                return False
            elif z.key==x.key:
                return True
            elif z.key<x.key:
                x=x.left
            else:
                x=x.right
                
def delete(T,z,i):
    if i==0:
        x=T
        y=None
        while 1:    
            y=x
            if x is None:
                return 
            elif z.key==x.key:
                break
            elif z.key<x.key:
                x=x.left
            else:
                x=x.right
            z.parent=y
        z=x     
    if z.left is None and z.right is None:
        if z is z.parent.right:
            z.parent.right=None
        else:
            z.parent.left=None
    elif z.left is None:
        if z is z.parent.left:
            z.parent.left=z.right
            z.right.parent=z.parent
        else:
            z.parent.right=z.right
            z.right.parent=z.parent
    elif z.right is None:
        if z is z.parent.left:
            z.parent.left=z.left
            z.left.parent=z.parent
        else:
            z.parent.right=z.left
            z.left.parent=z.parent
    else:
        y=del_inorder(z)
        z.key=y.key
        delete(T,y,1)
           
def preorder(u):
    if u is None:
        return
    pripre.append(str(u.key))
    preorder(u.left)
    preorder(u.right)

def inorder(u):
    if u is None:
        return
    inorder(u.left)
    priin.append(str(u.key))
    inorder(u.right)
    
def del_inorder(u):
    if u is None:
        return
    del_inorder(u.left)
    Min.append(u)
    del_inorder(u.right)
    return Min[0]

m=input()
root=None
for i in xrange(m):
    cmd=map(str,raw_input().split())
    if cmd[0]=="print":
        pripre=[]
        priin=[]
        preorder(root)
        inorder(root)
        print(' '+' '.join(priin))
        print(' '+' '.join(pripre))
    elif cmd[0]=="find":
        key=int(cmd[1])
        z=node(key)
        if find(root,z):
            print('yes')
        else:
            print('no')
    elif cmd[0]=='delete':
        Min=[]
        key=int(cmd[1])
        z=node(key)
        delete(root,z,0)
    else:
        key=int(cmd[1])
        z=node(key)
        root=insert(root,z)