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:
import sys
readline = sys.stdin.readline
class Node:
    __slots__ = ['value', 'p', 'left', 'right']
    def __init__(self, value = None, p = None, left = None, right = None):
        self.value = value
        self.p = p
        self.left = left
        self.right = right
class BinTree:
    __slots__ = ['_tree', 'result']
    def __init__(self):
        self._tree = None
    def insert(self, value):
        p = None
        c = self._tree
        while c is not None:
            p = c
            if value < c.value:
                c = c.left
            else:
                c = c.right
        if p is None:
            self._tree = Node(value)
        elif value < p.value:
            p.left = Node(value, p)
        else:
            p.right = Node(value, p)
    def find(self, value):
        c = self._tree
        while c is not None:
            if value == c.value:
                return True
            elif value < c.value:
                c = c.left
            else:
                c = c.right
        return False
    def delete(self, value):
        c = self._tree
        while c is not None:
            if value == c.value:
                if c.left is None and c.right is None:
                    if c.p.left is c:
                        c.p.left = None
                    else:
                        c.p.right = None
                elif c.left is not None and c.right is not None:
                    if c.right.left is None:
                        c.p.left = c.right
                        c.right.left = c.left
                        c.right.p = c.p
                    else:
                        c.value, c.right.left.value = c.right.left.value, c.value
                        self.delete(c.value)
                        return
                elif c.left is not None:
                    if c.p.left is c:
                        c.p.left = c.left
                    else:
                        c.p.right = c.left
                    c.left.p = c.p
                elif c.right is not None:
                    if c.p.right is c:
                        c.p.right = c.right
                    else:
                        c.p.left = c.right
                    c.right.p = c.p
                c = None
                return
            elif value < c.value:
                c = c.left
            else:
                c = c.right
    def preoder_walk(self):
        self.result = []
        def preoder(node):
            if node is not None:
                self.result.append(node.value)
                preoder(node.left)
                preoder(node.right)
        preoder(self._tree)
        print(" " + " ".join(map(str, self.result)))
    def inorder_walk(self):
        self.result = []
        def inorder(node):
            if node is not None:
                inorder(node.left)
                self.result.append(node.value)
                inorder(node.right)
        inorder(self._tree)
        print(" " + " ".join(map(str, self.result)))
n = int(input())
tree = BinTree()
for _ in range(n):
    com = readline().split()
    if com[0] == "insert":
        tree.insert(int(com[1]))
    elif com[0] == "find":
        print("yes" if tree.find(int(com[1])) else "no")
    elif com[0] == "delete":
        tree.delete(int(com[1]))
    else:
        tree.inorder_walk()
        tree.preoder_walk()

Submission status: Runtime Error

Solution code:
import sys
readline = sys.stdin.readline
class Node:
    __slots__ = ['value', 'left', 'right']
    def __init__(self, value = None, left = None, right = None):
        self.value = value
        self.left = left
        self.right = right
class BinTree:
    __slots__ = ['_tree', 'result']
    def __init__(self):
        self._tree = None
    def insert(self, value):
        p = None
        c = self._tree
        while c is not None:
            p = c
            if value < c.value:
                c = c.left
            else:
                c = c.right
        if p is None:
            self._tree = Node(value)
        elif value < p.value:
            p.left = Node(value)
        else:
            p.right = Node(value)
    def find(self, value):
        c = self._tree
        while c is not None:
            if value == c.value:
                return True
            elif value < c.value:
                c = c.left
            else:
                c = c.right
        return False
    def delete(self, value):
        def node_move(p, c, a):
            if p.left == c:
                p.left = a
            else:
                p.right = a
        c = self._tree
        p = Node(None, c)
        while c.value != value:
            p = c
            if c is None:
                return
            if value < c.value:
                c = c.left
            else:
                c = c.right
        if c.left is None:
            node_move(p, c, c.right)
        elif c.right is None or c.right.left is None:
            node_move(p, c, c.left)
        else:
            q = c.right
            while q.left.left is not None:
                q = q.left
            c.value = q.left.value
            q.left = q.left.right
        return
    def preoder_walk(self):
        self.result = []
        def preoder(node):
            if node is not None:
                self.result.append(node.value)
                preoder(node.left)
                preoder(node.right)
        preoder(self._tree)
        print(" " + " ".join(map(str, self.result)))
    def inorder_walk(self):
        self.result = []
        def inorder(node):
            if node is not None:
                inorder(node.left)
                self.result.append(node.value)
                inorder(node.right)
        inorder(self._tree)
        print(" " + " ".join(map(str, self.result)))
n = int(input())
tree = BinTree()
for _ in range(n):
    com = readline().split()
    if com[0] == "insert":
        tree.insert(int(com[1]))
    elif com[0] == "find":
        print("yes" if tree.find(int(com[1])) else "no")
    elif com[0] == "delete":
        tree.delete(int(com[1]))
    else:
        tree.inorder_walk()
        tree.preoder_walk()

Submission status: Runtime Error

Solution code:
import sys
readline = sys.stdin.readline
class Node:
    __slots__ = ['value', 'left', 'right']
    def __init__(self, value = None, left = None, right = None):
        self.value = value
        self.left = left
        self.right = right
class BinTree:
    __slots__ = ['_tree', 'result']
    def __init__(self):
        self._tree = None
    def insert(self, value):
        p = None
        c = self._tree
        while c is not None:
            p = c
            if value < c.value:
                c = c.left
            else:
                c = c.right
        if p is None:
            self._tree = Node(value)
        elif value < p.value:
            p.left = Node(value)
        else:
            p.right = Node(value)
    def find(self, value):
        c = self._tree
        while c is not None:
            if value == c.value:
                return True
            elif value < c.value:
                c = c.left
            else:
                c = c.right
        return False
    def delete(self, value):
        def node_move(p, c, a):
            if p.left == c:
                p.left = a
            else:
                p.right = a
        c = self._tree
        p = Node(None, c)
        while c.value != value:
            p = c
            if c is None:
                return
            if value < c.value:
                c = c.left
            else:
                c = c.right
        if c.left is None:
            node_move(p, c, c.right)
        elif c.right is None or c.right.left is None:
            node_move(p, c, c.left)
        elif c.right.left is None:
            c.right.left = c.left
            node_move(p, c, c.right)
        else:
            q = c.right
            while q.left.left is not None:
                q = q.left
            c.value = q.left.value
            q.left = q.left.right
        return
    def preoder_walk(self):
        self.result = []
        def preoder(node):
            if node is not None:
                self.result.append(node.value)
                preoder(node.left)
                preoder(node.right)
        preoder(self._tree)
        print(" " + " ".join(map(str, self.result)))
    def inorder_walk(self):
        self.result = []
        def inorder(node):
            if node is not None:
                inorder(node.left)
                self.result.append(node.value)
                inorder(node.right)
        inorder(self._tree)
        print(" " + " ".join(map(str, self.result)))
n = int(input())
tree = BinTree()
for _ in range(n):
    com = readline().split()
    if com[0] == "insert":
        tree.insert(int(com[1]))
    elif com[0] == "find":
        print("yes" if tree.find(int(com[1])) else "no")
    elif com[0] == "delete":
        tree.delete(int(com[1]))
    else:
        tree.inorder_walk()
        tree.preoder_walk()

Submission status: Runtime Error

Solution code:
import sys
readline = sys.stdin.readline
class Node:
    __slots__ = ['value', 'left', 'right']
    def __init__(self, value = None, left = None, right = None):
        self.value = value
        self.left = left
        self.right = right
class BinTree:
    __slots__ = ['_tree', 'result']
    def __init__(self):
        self._tree = None
    def insert(self, value):
        p = None
        c = self._tree
        while c is not None:
            p = c
            if value < c.value:
                c = c.left
            else:
                c = c.right
        if p is None:
            self._tree = Node(value)
        elif value < p.value:
            p.left = Node(value)
        else:
            p.right = Node(value)
    def find(self, value):
        c = self._tree
        while c is not None:
            if value == c.value:
                return True
            elif value < c.value:
                c = c.left
            else:
                c = c.right
        return False
    def delete(self, value):
        def node_move(p, c, a):
            if p.left == c:
                p.left = a
            else:
                p.right = a
        p = None
        c = self._tree
        while c.value != value:
            p = c
            if c is None:
                return
            if value < c.value:
                c = c.left
            else:
                c = c.right
        if c.left is None:
            node_move(p, c, c.right)
        elif c.right is None or c.right.left is None:
            node_move(p, c, c.left)
        elif c.right.left is None:
            c.right.left = c.left
            node_move(p, c, c.right)
        else:
            q = c.right
            while q.left.left is not None:
                q = q.left
            c.value = q.left.value
            q.left = q.left.right
        return
    def preoder_walk(self):
        self.result = []
        def preoder(node):
            if node is not None:
                self.result.append(node.value)
                preoder(node.left)
                preoder(node.right)
        preoder(self._tree)
        print(" " + " ".join(map(str, self.result)))
    def inorder_walk(self):
        self.result = []
        def inorder(node):
            if node is not None:
                inorder(node.left)
                self.result.append(node.value)
                inorder(node.right)
        inorder(self._tree)
        print(" " + " ".join(map(str, self.result)))
n = int(input())
tree = BinTree()
for _ in range(n):
    com = readline().split()
    if com[0] == "insert":
        tree.insert(int(com[1]))
    elif com[0] == "find":
        print("yes" if tree.find(int(com[1])) else "no")
    elif com[0] == "delete":
        tree.delete(int(com[1]))
    else:
        tree.inorder_walk()
        tree.preoder_walk()

Submission status: Runtime Error

Solution code:
import collections
sent = -1

def insert(hoge, new_node, root):
    #print(hoge)
    parent_maybe = sent
    now_looking = root
    hoge[new_node]['node_id'] = new_node
    while now_looking != sent:
        parent_maybe = now_looking
        if new_node < hoge[now_looking]['node_id']:
            now_looking = hoge[now_looking]['left']
        else:
            now_looking = hoge[now_looking]['right']
    hoge[new_node]['parent'] = parent_maybe
    
    if parent_maybe == sent:
        root = new_node
        hoge[new_node]['parent'] = sent
        hoge[new_node]['left'] = sent
        hoge[new_node]['right'] = sent
    elif new_node < hoge[parent_maybe]['node_id']:
        hoge[parent_maybe]['left'] = new_node
        hoge[new_node]['left'] = sent
        hoge[new_node]['right'] = sent
    else:
        hoge[parent_maybe]['right'] = new_node
        hoge[new_node]['left'] = sent
        hoge[new_node]['right'] =sent
    
    return root
    
def inorder(node_id):
    if node_id == sent:
        return None
    inorder(hoge[node_id]['left'])
    print(' {}'.format(node_id), end='')
    inorder(hoge[node_id]['right'])

def preorder(node_id):
    if node_id == sent:
        return None
    print(' {}'.format(node_id), end='')
    preorder(hoge[node_id]['left'])
    preorder(hoge[node_id]['right'])
    
    
def getTree(root):
    inorder(root)
    print()
    preorder(root)
    print()
    
def searchNode(hoge, num, node_id):
    if node_id == sent:
        return 'no'
    
    if num == node_id:
        return 'yes'
    elif num < node_id:
        return searchNode(hoge, num, hoge[node_id]['left'])
    elif num > node_id:
        return searchNode(hoge, num, hoge[node_id]['right'])

def deleteNode(hoge, node_id):
    left_child = hoge[node_id]['left']
    right_child = hoge[node_id]['right']
    parent = hoge[node_id]['parent']
    if left_child == sent and right_child == sent:
        if hoge[parent]['left'] == node_id:
            hoge[parent]['left'] = sent
        else:
            hoge[parent]['right'] = sent
    elif left_child == sent and right_child != sent:
        if hoge[parent]['left'] == node_id:
            hoge[parent]['left'] = right_child
        else:
            hoge[parent]['right'] = right_child 
        hoge[right_child]['parent'] = parent
    elif right_child == sent and left_child != sent:
        if hoge[parent]['left'] == node_id:
            hoge[parent]['left'] == left_child
        else:
            hoge[parent]['right'] == left_child
        hoge[left_child]['parent'] = parent
    else:
        min_node = getMin(hoge, node_id)
        hoge[left_child]['parent'] = min_node
        hoge[right_child]['parent'] = min_node
        hoge[min_node]['left'] = left_child
        hoge[min_node]['right'] = right_child
        min_parent = hoge[min_node]['parent']
        if hoge[min_node]['right'] == sent:
            hoge[min_parent]['left'] = sent
        else:
            min_node_rchild = hoge[min_node]['right']
            hoge[min_parent]['left'] = min_node_rchild
            hoge[min_node_rchild]['parent'] = min_parent
    del hoge[node_id]
        
def getMin(hoge, node_id):
    while hoge[node_id]['left'] != sent:
        node_id = hoge[node_id]['left']
    return node_id

if __name__ == '__main__':
    num = int(input())
    hoge = collections.defaultdict(dict)
    root = -1
    for _ in range(num):
        command = input()
        if command.split()[0] == 'insert':
            root = insert(hoge, int(command.split()[1]), root)
        elif command.split()[0] == 'find':
            print(searchNode(hoge, int(command.split()[1]), root))
        elif command.split()[0] == 'delete':
            deleteNode(hoge, int(command.split()[1]))
        else:
            getTree(root)

Submission status: Runtime Error

Solution code:
import collections
sent = None

def insert(hoge, new_node, root):
    parent_maybe = sent
    now_looking = root
    hoge[new_node]['node_id'] = new_node
    while now_looking != sent:
        parent_maybe = now_looking
        if new_node < hoge[now_looking]['node_id']:
            now_looking = hoge[now_looking]['left']
        else:
            now_looking = hoge[now_looking]['right']
    hoge[new_node]['parent'] = parent_maybe
    
    if parent_maybe == sent:
        root = new_node
        hoge[new_node]['parent'] = sent
        hoge[new_node]['left'] = sent
        hoge[new_node]['right'] = sent
    elif new_node < hoge[parent_maybe]['node_id']:
        hoge[parent_maybe]['left'] = new_node
        hoge[new_node]['left'] = sent
        hoge[new_node]['right'] = sent
    else:
        hoge[parent_maybe]['right'] = new_node
        hoge[new_node]['left'] = sent
        hoge[new_node]['right'] =sent
    
    return root
    
def inorder(node_id):
    if node_id == sent:
        return None
    inorder(hoge[node_id]['left'])
    print(' {}'.format(node_id), end='')
    inorder(hoge[node_id]['right'])

def preorder(node_id):
    if node_id == sent:
        return None
    print(' {}'.format(node_id), end='')
    preorder(hoge[node_id]['left'])
    preorder(hoge[node_id]['right'])
    
    
def getTree(root):
    inorder(root)
    print()
    preorder(root)
    print()
    
def searchNode(hoge, num, node_id):
    if node_id == sent:
        return 'no'
    
    if num == node_id:
        return 'yes'
    elif num < node_id:
        return searchNode(hoge, num, hoge[node_id]['left'])
    elif num > node_id:
        return searchNode(hoge, num, hoge[node_id]['right'])

def deleteNode(hoge, node_id):
    left_child = hoge[node_id]['left']
    right_child = hoge[node_id]['right']
    parent = hoge[node_id]['parent']
    if left_child == sent and right_child == sent:
        if hoge[parent]['left'] == node_id:
            hoge[parent]['left'] = sent
        else:
            hoge[parent]['right'] = sent
    elif left_child == sent and right_child != sent:
        if hoge[parent]['left'] == node_id:
            hoge[parent]['left'] = right_child
        else:
            hoge[parent]['right'] = right_child 
        hoge[right_child]['parent'] = parent
    elif right_child == sent and left_child != sent:
        if hoge[parent]['left'] == node_id:
            hoge[parent]['left'] = left_child
        else:
            hoge[parent]['right'] == left_child
        hoge[left_child]['parent'] = parent
    else:
        min_node = getMin(hoge, hoge[node_id]['right'])
        min_parent = hoge[min_node]['parent']
        if hoge[min_node]['right'] == sent:
            flag = True
        else:
            flag = False
        hoge[left_child]['parent'] = min_node
        hoge[right_child]['parent'] = min_node
        hoge[min_node]['left'] = left_child
        if min_node != right_child:
            hoge[min_node]['right'] = right_child
        hoge[min_node]['parent'] = parent
        if hoge[parent]['left'] == node_id:
            hoge[parent]['left'] = min_node
        else:
            hoge[parent]['right'] = min_node
            
        if flag:
            hoge[min_parent]['left'] = sent
        else:
            min_node_rchild = hoge[min_node]['right']
            hoge[min_parent]['left'] = min_node_rchild
            hoge[min_node_rchild]['parent'] = min_parent
    del hoge[node_id]
        
def getMin(hoge, node_id):
    while hoge[node_id]['left'] != sent:
        node_id = hoge[node_id]['left']
    return node_id

if __name__ == '__main__':
    num = int(input())
    hoge = collections.defaultdict(dict)
    root = sent
    for _ in range(num):
        command = input()
        #print(command)
        if command.split()[0] == 'insert':
            root = insert(hoge, int(command.split()[1]), root)
        elif command.split()[0] == 'find':
            print(searchNode(hoge, int(command.split()[1]), root))
        elif command.split()[0] == 'delete':
            deleteNode(hoge, int(command.split()[1]))
        else:
            getTree(root)
        #print(hoge)
        #print()

Submission status: Runtime Error

Solution code:
import collections
sent = None

def insert(hoge, new_node, root):
    parent_maybe = sent
    now_looking = root
    hoge[new_node]['node_id'] = new_node
    while now_looking != sent:
        parent_maybe = now_looking
        #print(hoge[now_looking], now_looking)
        if new_node < hoge[now_looking]['node_id']:
            now_looking = hoge[now_looking]['left']
        else:
            now_looking = hoge[now_looking]['right']
    hoge[new_node]['parent'] = parent_maybe
    
    if parent_maybe == sent:
        root = new_node
        hoge[new_node]['parent'] = sent
        hoge[new_node]['left'] = sent
        hoge[new_node]['right'] = sent
    elif new_node < hoge[parent_maybe]['node_id']:
        hoge[parent_maybe]['left'] = new_node
        hoge[new_node]['left'] = sent
        hoge[new_node]['right'] = sent
    else:
        hoge[parent_maybe]['right'] = new_node
        hoge[new_node]['left'] = sent
        hoge[new_node]['right'] =sent
    
    return root
    
def inorder(node_id):
    if node_id == sent:
        return None
    inorder(hoge[node_id]['left'])
    print(' {}'.format(node_id), end='')
    inorder(hoge[node_id]['right'])

def preorder(node_id):
    if node_id == sent:
        return None
    print(' {}'.format(node_id), end='')
    preorder(hoge[node_id]['left'])
    preorder(hoge[node_id]['right'])
    
    
def getTree(root):
    inorder(root)
    print()
    preorder(root)
    print()
    
def searchNode(hoge, num, node_id):
    if node_id == sent:
        return 'no'
    
    if num == node_id:
        return 'yes'
    elif num < node_id:
        return searchNode(hoge, num, hoge[node_id]['left'])
    elif num > node_id:
        return searchNode(hoge, num, hoge[node_id]['right'])

def deleteNode(hoge, node_id):
    left_child = hoge[node_id]['left']
    right_child = hoge[node_id]['right']
    parent = hoge[node_id]['parent']
    if left_child == sent and right_child == sent:
        if hoge[parent]['left'] == node_id:
            hoge[parent]['left'] = sent
        else:
            hoge[parent]['right'] = sent
    elif left_child == sent and right_child != sent:
        if hoge[parent]['left'] == node_id:
            hoge[parent]['left'] = right_child
        else:
            hoge[parent]['right'] = right_child 
        hoge[right_child]['parent'] = parent
    elif right_child == sent and left_child != sent:
        if hoge[parent]['left'] == node_id:
            hoge[parent]['left'] = left_child
        else:
            hoge[parent]['right'] == left_child
        hoge[left_child]['parent'] = parent
    else:
        min_node = getMin(hoge, hoge[node_id]['right'])
        min_parent = hoge[min_node]['parent']
        if hoge[min_node]['right'] == sent:
            flag = True
        else:
            flag = False
        hoge[left_child]['parent'] = min_node
        hoge[right_child]['parent'] = min_node
        hoge[min_node]['left'] = left_child
        if min_node != right_child:
            hoge[min_node]['right'] = right_child
        hoge[min_node]['parent'] = parent
        if hoge[parent]['left'] == node_id:
            hoge[parent]['left'] = min_node
        else:
            hoge[parent]['right'] = min_node
            
        if flag:
            hoge[min_parent]['left'] = sent
        else:
            min_node_rchild = hoge[min_node]['right']
            hoge[min_parent]['left'] = min_node_rchild
            hoge[min_node_rchild]['parent'] = min_parent
    del hoge[node_id]
        
def getMin(hoge, node_id):
    while hoge[node_id]['left'] != sent:
        node_id = hoge[node_id]['left']
    return node_id

if __name__ == '__main__':
    num = int(input())
    hoge = collections.defaultdict(dict)
    root = sent
    for _ in range(num):
        command = input()
        #print(command)
        if command.split()[0] == 'insert':
            root = insert(hoge, int(command.split()[1]), root)
        elif command.split()[0] == 'find':
            print(searchNode(hoge, int(command.split()[1]), root))
        elif command.split()[0] == 'delete':
            deleteNode(hoge, int(command.split()[1]))
        else:
            getTree(root)

Submission status: Runtime Error

Solution code:
# Binary Search Tree
class Node:
    def __init__(self, v):
        self.value = v
        self.parent = None
        self.left = None
        self.right = None

# 再帰を使わないパターンの方が早い
def insert(node):
    global root
    y = None
    x = root
    while x is not None:
        y = x
        if node.value < x.value:
            x = x.left
        else:
            x = x.right
    node.parent = y
    if y is None:
        root = node
    elif node.value < y.value:
        y.left = node
    else:
        y.right = node

def find(num):
    global root
    x = root
    while x is not None:
        if num == x.value:
            return True
        elif num < x.value:
            x = x.left
        else:
            x = x.right
    return False

def delete(num):
    global root
    y = None # xの親
    x = root
    isLeft = False
    while x is not None:
        if num == x.value:
            break
        elif num < x.value:
            x = x.left
            isLeft = True
        else:
            x = x.right
            isLeft = False
        y = x
    if x is None:
        return
    if x.left is None and x.right is None:
        if x.parent is not None:
            if isLeft:
                x.parent.left = None
            else:
                x.parent.right = None
    elif x.left is None:
        if x.parent is not None:
            if isLeft:
                x.parent.left = x.right
            else:
                x.parent.right = x.right
            x.right.parent = x.parent
    elif x.right is None:
        if x.parent is not None:
            if isLeft:
                x.parent.left = x.left
            else:
                x.parent.right = x.left
            x.left.parent = x.parent
    else:
        delete(x.left.value)
        x.value = x.left.value

def preorder_walk(node):
    if node:
        yield node.value
        for x in preorder_walk(node.left):
            yield x
        for x in preorder_walk(node.right):
            yield x

def inorder_walk(node):
    if node:
        for x in inorder_walk(node.left):
            yield x
        yield node.value
        for x in inorder_walk(node.right):
            yield x

root = None
n = int(input())
for i in range(n):
    cmd, *val = input().split()
    if cmd == "insert":
        #root = insert(root, int(val[0]))
        insert(Node(int(val[0])))
    elif cmd == "print":
        print("", *inorder_walk(root))
        print("", *preorder_walk(root))
    elif cmd == "find":
        if find(int(val[0])):
            print("yes")
        else:
            print("no")
    elif cmd == "delete":
        delete(int(val[0]))