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: Accepted

Solution code:
# -*- coding: utf-8 -*-


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


class BinarySearchTree(list):
    def __init__(self):
        list.__init__(self)
        self.root = None

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

    def preorder(self):
        def preParse(u):
            if u == None:
                return
            print(" " + str(u.key), end="")
            preParse(u.left)
            preParse(u.right)
        preParse(self.root)
        print("")

    def inorder(self):
        def inParse(u):
            if u == None:
                return
            inParse(u.left)
            print(" " + str(u.key), end="")
            inParse(u.right)
        inParse(self.root)
        print("")

    def print(self):
        self.inorder()
        self.preorder()

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

    def delete(self, z):
        # y is delete node.
        if z.left is None or z.right is None:
            y = z
        else:
            y = self.getSuccessor(z)
        
        if y.left is not None:
            x = y.left
        else:
            x = y.right
        
        if x is not None:
            x.parent = y.parent

        if y.parent is None:
            self.root = x
        elif y == y.parent.left:
            y.parent.left = x
        else:
            y.parent.right = x
        
        if y != z:
            z.key = y.key

        

    def getSuccessor(self, x):
        if x.right is not None:
            return self.getMinimum(x.right)

        y = x.parent
        while y is not None and x == y.right:
            x = y
            y = y.parent
        return y

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


if __name__ == '__main__':

    n = int(input())
    command = [input().split(" ") for _ in range(n)]
    T = BinarySearchTree()

    for c in command:
        if c[0] == "insert":
            T.insert(int(c[1]))
        elif c[0] == "find":
            z = T.find(int(c[1]))
            if z is None:
                print("no")
            else:
                print("yes")
        elif c[0] == "delete":
            z = T.find(int(c[1]))
            T.delete(z)
        else:
            T.print()

Submission status: Accepted

Solution code:
LEFT = 0
RIGHT = 1

class Node:

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

class BTree:

    def __init__(self):
        self.root = None

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

    def find(self, key):
        current = self.root
        while current is not None:
            if current.key == key:
                print("yes")
                return

            if key < current.key:
                current = current.left
            else:
                current = current.right

        print("no")
        return

    def find_successor(self, node):
        current = node.right

        while current.left is not None:
            current = current.left

        return current

    def delete(self, key):
        current = self.root
        parent = None
        parent_lr = None
        while current.key != key:
            if key < current.key:
                parent = current
                parent_lr = LEFT
                current = current.left
            else:
                parent = current
                parent_lr = RIGHT
                current = current.right

            if current is None:
                return None

        if current.left is None and current.right is None:
            if parent_lr == LEFT:
                parent.left = None
            else:
                parent.right = None

        elif current.left is None and current.right is not None:
            if parent_lr == LEFT:
                parent.left = current.right
            else:
                parent.right = current.right

        elif current.left is not None and current.right is None:
            if parent_lr == LEFT:
                parent.left = current.left
            else:
                parent.right = current.left

        else:
            successor = self.find_successor(current)
            new_key = successor.key
            self.delete(successor.key)
            current.key = new_key

        del current


    def print_inorder(self):

        def print_inorder_innner(root):
            if root.left is not None:
                print_inorder_innner(root.left)
            print(" {0}".format(root.key), end="")
            if root.right is not None:
                print_inorder_innner(root.right)

        print_inorder_innner(self.root)
        print("")

    def print_preorder(self):

        def print_preorder_innner(root):
            print(" {0}".format(root.key), end="")

            if root.left is not None:
                print_preorder_innner(root.left)
            if root.right is not None:
                print_preorder_innner(root.right)

        print_preorder_innner(self.root)
        print("")

    def debug_print(self):

        def debug_print_inner(root):
            if root.left is None:
                lstr = "None"
            else:
                lstr = "{0:4d}".format(root.left.key)

            if root.right is None:
                rstr = "None"
            else:
                rstr = "{0:4d}".format(root.right.key)

            print("{0:4d} : {1} , {2}".format(root.key, lstr, rstr))

            if root.left is not None:
                debug_print_inner(root.left)

            if root.right is not None:
                debug_print_inner(root.right)

        root = self.root
        debug_print_inner(root)


if __name__ == '__main__':
    btree = BTree()

    n = int(input())
    inst = []
    for _ in range(n):
        al = input().split()
        if al[0] == "print":
            inst.append(("print", 0))
        elif al[0] == "debug":
            inst.append(("debug", 0))
        else:
            inst.append((al[0], int(al[1])))

    for (i, k) in inst:

        if i == "insert":
            btree.insert(Node(k))
        elif i == "find":
            btree.find(k)
        elif i == "delete":
            btree.delete(k)
        elif i == "debug":
            btree.debug_print()
        else:
            btree.print_inorder()
            btree.print_preorder()

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
from copy import deepcopy, copy
class Node:
    __slots__ = ['value', 'left', 'right']
    def __init__(self, value=None):
        self.value = value
        self.left = None
        self.right = None
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):
        parent = None
        current = self._tree
        while current.value != value:
            parent = current
            if current is None:
                return
            elif value < current.value:
                current = current.left
            else:
                current = current.right
        if current.left is None and current.right is None:
            if parent.left is current:
                parent.left = None
            else:
                parent.right = None
        elif current.left is None:
            if parent.left is current:
                parent.left = current.right
            else:
                parent.right = current.right
        elif current.right is None:
            if parent.left is current:
                parent.left = current.left
            else:
                parent.right = current.left
        else:
            next_node_parent = current
            next_node = current.right
            while next_node.left is not None:
                next_node_parent = next_node
                next_node = next_node.left
            if next_node.right is None:
                if next_node_parent.left is next_node:
                    next_node_parent.left = None
                else:
                    next_node_parent.right = None
            else:
                if next_node_parent.left is next_node:
                    next_node_parent.left = next_node.right
                else:
                    next_node_parent.right = next_node.right
            current.value = next_node.value
    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: Accepted

Solution code:
import sys
readline = sys.stdin.readline
class Node:
    __slots__ = ['value', 'left', 'right']
    def __init__(self, value=None):
        self.value = value
        self.left = None
        self.right = None
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):
        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:
            if p.left == c:
                p.left = c.right
            else:
                p.right = c.right
        elif c.right is None:
            if p.left == c:
                p.left = c.left
            else:
                p.right = c.left
        elif c.right.left is None:
            c.right.left = c.left
            if p.left == c:
                p.left = c.right
            else:
                p.right = 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: Accepted

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:
            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: Accepted

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:
            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: Accepted

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:
            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
    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: Accepted

Solution code:
import sys

class Node:
    __slots__ = ['key', 'left', 'right']
    def __init__(self, key):
        self.key = key
        self.left = self.right = None

root = None

def insert(key):
    global root
    x, y = root, None
    while x is not None: x, y = x.left if key < x.key else x.right, x
    if y is None: root = Node(key)
    elif key < y.key: y.left = Node(key)
    else: y.right = Node(key)

def find(target):
    result = root
    while result and target != result.key:
        result = result.left if target < result.key else result.right
    return result is None

def delete(target):
    def remove_node(p, c, a):
        if p.left == c: p.left = a
        else: p.right = a
    p, c = None, root
    while c.key != target: p, c = c, c.left if target < c.key else c.right
    if c.left is None:
        remove_node(p, c, c.right)
    elif c.right is None:
        remove_node(p, c, c.left)
    elif c.right.left is None:
        c.right.left = c.left
        remove_node(p, c, c.right)
    else:
        g = c.right
        while g.left.left is not None: g = g.left
        c.key = g.left.key
        g.left = g.left.right

def inorder(node):
    return inorder(node.left) + f' {node.key}' + inorder(node.right) if node else ''
def preorder(node):
    return f' {node.key}' + preorder(node.left) + preorder(node.right) if node else ''

input()
for e in sys.stdin:
    if e[0] == 'i': insert(int(e[7:]))
    elif e[0] == 'd': delete(int(e[7:]))
    elif e[0] == 'f': print(['yes','no'][find(int(e[5:]))])
    else: print(inorder(root)); print(preorder(root))

Submission status: Accepted

Solution code:
import sys

class Node:
    __slots__ = ['key', 'left', 'right']
    def __init__(self, key):
        self.key = key
        self.left = self.right = None

root = None

def insert(key):
    global root
    x, y = root, None
    while x is not None: x, y = x.left if key < x.key else x.right, x
    if y is None: root = Node(key)
    elif key < y.key: y.left = Node(key)
    else: y.right = Node(key)

def find(target):
    result = root
    while result and target != result.key:
        result = result.left if target < result.key else result.right
    return result is None

def delete(target):
    def remove_node(p, c, a):
        if p.left == c: p.left = a
        else: p.right = a
    p, c = None, root
    while c.key != target: p, c = c, c.left if target < c.key else c.right
    if c.left is None:
        remove_node(p, c, c.right)
    elif c.right is None:
        remove_node(p, c, c.left)
    elif c.right.left is None:
        c.right.left = c.left
        t = c.right.right
        c.key = c.right.key
        c.right = t
    else:
        g = c.right
        while g.left.left is not None: g = g.left
        c.key = g.left.key
        g.left = g.left.right

def inorder(node):
    return inorder(node.left) + f' {node.key}' + inorder(node.right) if node else ''
def preorder(node):
    return f' {node.key}' + preorder(node.left) + preorder(node.right) if node else ''

input()
for e in sys.stdin:
    if e[0] == 'i': insert(int(e[7:]))
    elif e[0] == 'd': delete(int(e[7:]))
    elif e[0] == 'f': print(['yes','no'][find(int(e[5:]))])
    else: print(inorder(root)); print(preorder(root))

Submission status: Accepted

Solution code:
import sys

class Node:
    __slots__ = ['key', 'left', 'right']
    def __init__(self, key):
        self.key = key
        self.left = self.right = None

root = None

def insert(key):
    global root
    x, y = root, None
    while x is not None: x, y = x.left if key < x.key else x.right, x
    if y is None: root = Node(key)
    elif key < y.key: y.left = Node(key)
    else: y.right = Node(key)

def find(target):
    result = root
    while result and target != result.key:
        result = result.left if target < result.key else result.right
    return result is None

def delete(target):
    def remove_node(p, c, a):
        if p.left == c: p.left = a
        else: p.right = a
    p, c = None, root
    while c.key != target: p, c = c, c.left if target < c.key else c.right
    if c.left is None:
        remove_node(p, c, c.right)
    elif c.right is None:
        remove_node(p, c, c.left)
    elif c.right.left is None:
        c.right.left = c.left
        c.key = c.right.key
        c.right = c.right.right
    else:
        g = c.right
        while g.left.left is not None: g = g.left
        c.key = g.left.key
        g.left = g.left.right

def inorder(node):
    return inorder(node.left) + f' {node.key}' + inorder(node.right) if node else ''
def preorder(node):
    return f' {node.key}' + preorder(node.left) + preorder(node.right) if node else ''

input()
for e in sys.stdin:
    if e[0] == 'i': insert(int(e[7:]))
    elif e[0] == 'd': delete(int(e[7:]))
    elif e[0] == 'f': print(['yes','no'][find(int(e[5:]))])
    else: print(inorder(root)); print(preorder(root))

Submission status: Accepted

Solution code:
# 03:35 sec    56176 KB     1570 bytes 
import sys

class Node:
    __slots__ = ['key', 'left', 'right']
    def __init__(self, key):
        self.key = key
        self.left = self.right = None

root = None

def insert(key):
    global root
    x, y = root, None
    while x: x, y = x.left if key < x.key else x.right, x
    if y is None: root = Node(key)
    elif key < y.key: y.left = Node(key)
    else: y.right = Node(key)

def find(target):
    result = root
    while result and target != result.key:
        result = result.left if target < result.key else result.right
    return result is None

def delete(target):
    def remove_node(p, c, a):
        if p.left == c: p.left = a
        else: p.right = a
    p, c = None, root
    while c.key != target: p, c = c, c.left if target < c.key else c.right
    if c.left is None:
        remove_node(p, c, c.right)
    elif c.right is None:
        remove_node(p, c, c.left)
    elif c.right.left is None:
        c.right.left = c.left
        remove_node(p, c, c.right)
    else:
        g = c.right
        while g.left.left: g = g.left
        c.key = g.left.key
        g.left = g.left.right

def inorder(node):
    return inorder(node.left) + f' {node.key}' + inorder(node.right) if node else ''
def preorder(node):
    return f' {node.key}' + preorder(node.left) + preorder(node.right) if node else ''

input()
for e in sys.stdin:
    if e[0] == 'i': insert(int(e[7:]))
    elif e[0] == 'd': delete(int(e[7:]))
    elif e[0] == 'f': print(['yes','no'][find(int(e[5:]))])
    else: print(inorder(root)); print(preorder(root))