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:
class NullNode():
    def __init__(self):
        self.id = None

null_node = NullNode()
class Node():
    def __init__(self, id):
        global null_node
        self.id = id
        self.parent = null_node
        self.left = null_node
        self.right =  null_node

def preorder(node, out_list=[]):
    if node.id is not None:
        out_list.append(str(node.id))
        out_list = preorder(node.left, out_list)
        out_list = preorder(node.right, out_list)
    return out_list

def inorder(node, out_list=[]):
    if node.id is not None:
        out_list = inorder(node.left, out_list)
        out_list.append(str(node.id))
        out_list = inorder(node.right, out_list)
    return out_list

def insert(node, root_node):
    temp_node_parent = root_node.parent
    temp_node = root_node

    while temp_node.id is not None:
        temp_node_parent = temp_node
        if node.id < temp_node.id:
            temp_node = temp_node.left
        else:
            temp_node = temp_node.right

    node.parent = temp_node_parent
    if node.id < temp_node_parent.id:
        temp_node_parent.left = node
    else:
        temp_node_parent.right = node

def find(id,root_node):
    node = root_node
    while node.id is not None:
        if id < node.id:
            node = node.left
        elif id > node.id:
            node = node.right
        else:
            print('yes')
            break
    else:
        print('no')

def get_successor(node):
    successor = node.right
    while(successor.left.id is not None):
        successor = successor.left
    return successor

def delete(id, root_node):
    global null_node
    node = root_node
    while node.id != id:
        if id < node.id:
            node = node.left
        else:
            node = node.right

    if node.left.id is None or node.right.id is None:
        del_node = node

    else:
        del_node = get_successor(node)
        node.id = del_node.id

    if del_node.left.id is not None:
        change_node = del_node.left
    else:
        change_node = del_node.right

    if change_node.id is not None:
        change_node.parent = del_node.parent

    if del_node.parent.id is None:
        root_node = change_node
    elif del_node.id == del_node.parent.left.id:
        del_node.parent.left = change_node
    else:
        del_node.parent.right = change_node




import sys

n = int(sys.stdin.readline())
input_lines = sys.stdin.readlines()
root_node = NullNode()
for i in range(n):
    input_line = input_lines[i].split()
    command = input_line[0]
    if command == 'insert':
        id = int(input_line[1])
        id_node = Node(id)
        if root_node.id is None:
            root_node = id_node
        else:
            insert(id_node, root_node)

    elif command == 'find':
        id = int(input_line[1])
        find(id, root_node)

    elif command == 'delete':
        id = int(input_line[1])
        delete(id, root_node)
    else:
        inorder_list = inorder(root_node, [])
        preorder_list = preorder(root_node, [])
        out = ' ' + ' '.join(inorder_list)
        print(out)
        out = ' ' + ' '.join(preorder_list)
        print(out)

Submission status: Accepted

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

    def preorder(self):
        ret = [self.key]
        if self.left:
            ret += self.left.preorder()
        if self.right:
            ret += self.right.preorder()
        return ret

    def inorder(self):
        ret = []
        if self.left:
            ret += self.left.inorder()
        ret += [self.key]
        if self.right:
            ret += self.right.inorder()
        return ret

    def find(self, k):
        if self.key == k:
            return self
        elif self.key < k:
            if self.right:
                return self.right.find(k)
            else:
                return None
        else:
            if self.left:
                return self.left.find(k)
            else:
                return None


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

    def insert(self, k):
        z = Node(k)
        y = None
        x = self.root
        while x:
            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 print(self):
        print('', ' '.join(map(str, self.root.inorder())))
        print('', ' '.join(map(str, self.root.preorder())))

    def find(self, k):
        if self.root is None:
            return None
        else:
            return self.root.find(k)

    def delete(self, k):
        z = self.find(k)
        if z.left is None:
            self.transparent(z, z.right)
        elif z.right is None:
            self.transparent(z, z.left)
        else:
            y = self.minimum(z.right)
            if y.parent != z:
                self.transparent(y, y.right)
                y.right = z.right
                y.right.parent = y
            self.transparent(z, y)
            y.left = z.left
            y.left.parent = y

    def successor(self, x):
        if x.right:
            return self.minimum(x.right)
        y = x.parent
        while y and x == y.right:
            x = y
            y = y.parent
        return y

    def minimum(self, x):
        while x.left:
            x = x.left
        return x

    def maximum(self, x):
        while x.right:
            x = x.right
        return x

    def transparent(self, u, v):
        if u.parent is None:
            self.root = v
        elif u == u.parent.left:
            u.parent.left = v
        else:
            u.parent.right = v
        if v:
            v.parent = u.parent


m = int(input())
tree = Tree()
for _ in range(m):
    s = input().split()
    if s[0] == "insert":
        tree.insert(int(s[1]))
    elif s[0] == "find":
        if tree.find(int(s[1])):
            print("yes")
        else:
            print("no")
    elif s[0] == "delete":
        tree.delete(int(s[1]))
    else:
        tree.print()

Submission status: Accepted

Solution code:
#coding:utf-8
N = int(input())
trees = [list(input().split()) for i in range(N)]

class BinaryTree:
    def __init__(self,key,p=None,l=None,r=None):
        self.key = key
        self.p = p
        self.l = l
        self.r = r

def Insert(root,z):
    y = None
    x = root
    while x != None:
        y = x
        if z.key < x.key:
            x = x.l
        else:
            x = x.r
    z.p = y

    if y == None:
        root = z
    elif z.key < y.key:
        y.l = z
    else:
        y.r = z
    return root

def preOrder(x):
    if x == None:
        return
    global preList
    preList.append(x.key)
    
    preOrder(x.l)
    preOrder(x.r)

def inOrder(x):
    if x == None:
        return
    inOrder(x.l)

    global inList
    inList.append(x.key)
    
    inOrder(x.r)

def Find(x,z):
    while x != None and z.key != x.key:
        y = x
        if z.key < x.key:
            x = x.l
        else:
            x = x.r
    return x


def Delete(x, z):
    if z.l == None or z.r == None:
        y = z
    else:
        y = getSuccessor(z)

    if y.l != None:
        x = y.l
    else:
        x = y.r

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

    if y.p == None:
        global root
        root = x
    elif y == y.p.l:
        y.p.l = x
    else:
        y.p.r = x
    if y != z:
        z.key = y.key
        
def getSuccessor(x):
    if x.r != None:
        return getMinimum(x.r)
    y = x.p
    while y != None and x == y.r:
        x = y
        y = y.p
    return y

def getMinimum(x):
    while x.l != None:
        x = x.l
    return x

root = None
for data in trees:
    if data[0] == "print":
        inList = []
        preList = []
        inOrder(root)
        a = " " + " ".join([str(num) for num in inList])
        print(a)

        preOrder(root)
        a = " " + " ".join([str(num) for num in preList])
        print(a)

    else:
        z = BinaryTree(int(data[1]))
        if data[0] == "insert":
            root = Insert(root,z)
        elif data[0] == "find":
            a = Find(root, z)
            if a == None:
                print("no")
            else:
                print("yes")
        elif data[0] == "delete":
            Delete(root, Find(root,z))

Submission status: Accepted

Solution code:
#coding:utf-8
N = int(input())
trees = [list(input().split()) for i in range(N)]

class BinaryTree:
    def __init__(self,key,p=None,l=None,r=None):
        self.key = key
        self.p = p
        self.l = l
        self.r = r

def Insert(root,z):
    y = None
    x = root
    while x != None:
        y = x
        if z.key < x.key:
            x = x.l
        else:
            x = x.r
    z.p = y

    if y == None:
        root = z
    elif z.key < y.key:
        y.l = z
    else:
        y.r = z
    return root

def preOrder(x):
    if x == None:
        return
    global preList
    preList.append(x.key)
    
    preOrder(x.l)
    preOrder(x.r)

def inOrder(x):
    if x == None:
        return
    inOrder(x.l)

    global inList
    inList.append(x.key)
    
    inOrder(x.r)

def Find(x,z):
    while x != None and z.key != x.key:
        y = x
        if z.key < x.key:
            x = x.l
        else:
            x = x.r
    return x


def Delete(x, z):
    if z.l == None or z.r == None:
        y = z
    else:
        y = getSuccessor(z)

    if y.l != None:
        x = y.l
    else:
        x = y.r

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

    if y.p == None:
        pass
    elif y == y.p.l:
        y.p.l = x
    else:
        y.p.r = x
    if y != z:
        z.key = y.key
        
def getSuccessor(x):
    if x.r != None:
        return getMinimum(x.r)
    y = x.p
    while y != None and x == y.r:
        x = y
        y = y.p
    return y

def getMinimum(x):
    while x.l != None:
        x = x.l
    return x

root = None
for data in trees:
    if data[0] == "print":
        inList = []
        preList = []
        inOrder(root)
        a = " " + " ".join([str(num) for num in inList])
        print(a)

        preOrder(root)
        a = " " + " ".join([str(num) for num in preList])
        print(a)

    else:
        z = BinaryTree(int(data[1]))
        if data[0] == "insert":
            root = Insert(root,z)
        elif data[0] == "find":
            a = Find(root, z)
            if a == None:
                print("no")
            else:
                print("yes")
        elif data[0] == "delete":
            Delete(root, Find(root,z))

Submission status: Accepted

Solution code:
import sys

tree={}
np = -1

home=0
tree[home]=[None, None, None]

def search(p, x):
    node_pos=[None,None]
    while p != None:
        tmp = tree[p]
        if tmp[0] == x:
            node_pos[0] = p
            return node_pos
        node_pos[1] = p
        if x < tmp[0]:
            p = tmp[1]
        else:
            p = tmp[2]
    return node_pos

def node(x):
    global np
    np += 1
    tree[np] = [x, None, None]
    return np

def insert(p, x):
    if p == None or np == -1: return node(x)
    tmp = tree[p]
    if x== tmp[0]: return p
    elif x<tmp[0]:
        tree[p][1]=insert(tmp[1],x)
    else:
        tree[p][2]=insert(tmp[2],x)
    return p

def deletenode(p, parent, child=None):
        if tree[parent][1]==p:
            tree[parent][1] = child
        elif tree[parent][2]==p:
            tree[parent][2] = child
        del tree[p]

def searchmin(p):
    while tree[p][1]!=None:
        p = tree[p][1]
    return p

def delete(x):
    p, parent = search(0,x)
    if tree[p][1:3]==[None,None]:
        deletenode(p,parent)
    elif tree[p][1]==None:
        deletenode(p, parent, tree[p][2])
    elif tree[p][2]==None:
        deletenode(p, parent, tree[p][1])
    else:
        p1=searchmin(tree[p][2])
        p1, parent1 = search(0,tree[p1][0])

        if tree[parent1][1]==p1:
            tree[parent1][1] = None
        elif tree[parent1][2]==p1:
            tree[parent1][2] = None

        if tree[parent][1]==p:
            tree[parent][1] = p1
        elif tree[parent][2]==p:
            tree[parent][2] = p1
        tree[p1][1]=tree[p][1]
        tree[p1][2]=tree[p][2]
        del tree[p]
    return

def preorder(p):
    if p == None: return []
    p1, p2 = tree[p][1:3]
    return [tree[p][0]] + preorder(p1) + preorder(p2)

def inorder(p):
    if p == None: return []
    p1, p2 = tree[p][1:3]
    return inorder(p1) + [tree[p][0]] +inorder(p2)

n = int(input())
i = 0
while i<n:
    s = raw_input()
    if s[0]=='i':
        p = insert(0,int(s[7:]))
    elif s[0]=='f':
        if search(0,int(s[5:]))[0]!=None: print 'yes'
        else: print 'no'
    elif s[0]=='d':
        delete(int(s[7:]))
    elif s[0]=='p':
        print ' ' + ' '.join(map(str, inorder(home)))
        print ' ' + ' '.join(map(str, preorder(home)))
    i += 1

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin


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


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


def tree_find(node, key):
    if not node:
        return None
    if node.key == key:
        return node
    if key < node.key:
        return tree_find(node.left, key)
    return tree_find(node.right, key)


def tree_delete(top, z):
    if z.left is None or z.right is None:
        y = z
    else:
        y = tree_successor(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:
        top = x
    elif y == y.parent.left:
        y.parent.left = x
    else:
        y.parent.right = x

    if y != z:
        z.key = y.key
    return top


def tree_successor(x):
    if x.right is not None:
        return tree_minimum(x.right)
    y = x.parent
    while y is not None and x == y.right:
        x = y
        y = y.parent
    return y


def tree_minimum(x):
    while x.left is not None:
        x = x.left
    return x


def inorder_walk(node):
    if node.left:
        inorder_walk(node.left)
    print('', node.key, end='')
    if node.right:
        inorder_walk(node.right)


def preorder_walk(node):
    print('', node.key, end='')
    if node.left:
        preorder_walk(node.left)
    if node.right:
        preorder_walk(node.right)


n = int(stdin.readline())
#assert n <= 500000

top = None
for _ in range(n):
    cmd = stdin.readline()
    if cmd.startswith('i'):
        key = int(cmd[7:])
        #assert -2000000000 <= key <= 2000000000
        top = tree_insert(top, Node(key))
    elif cmd.startswith('f'):
        key = int(cmd[5:])
        r = tree_find(top, key)
        print('yes' if r else 'no')
    elif cmd.startswith('d'):
        key = int(cmd[7:])
        node = tree_find(top, key)
        if node:
            top = tree_delete(top, node)
    else:
        inorder_walk(top)
        print()
        preorder_walk(top)
        print()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2**20)

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

def pre_parse(T: dict, u: int, pre_ls: list):
    if u is None:
        return
    pre_ls.append(u)
    pre_parse(T, T[u].left, pre_ls)
    pre_parse(T, T[u].right, pre_ls)

def in_parse(T: dict, u: int, in_ls: list):
    if u is None:
        return
    in_parse(T, T[u].left, in_ls)
    in_ls.append(u)
    in_parse(T, T[u].right, in_ls)


def insert(T: dict, ROOT: int , z: int):
    if ROOT == z:
        T[z] = Node()
    else:
        T[z] = Node()
        x = ROOT
        while x is not None: #子ノードがNoneになったらbreak
            next_parent = x
            if z < x: # 新たなノードが現在のノードより小さければ左の子ノードへ。
                x = T[x].left
            else:
                x = T[x].right
        T[z].parent = next_parent
        if z < next_parent: # 親より小さければ左の子ノードとして付ける
            T[next_parent].left = z
        else:
            T[next_parent].right = z

def find(T: dict, ROOT: int, k: int):
    """
    Tからkを見つけ出す。見つからなかったらNoneを返す
    """
    x = ROOT
    while x is not None and x != k:
        if k < x:
            x = T[x].left
        else:
            x = T[x].right
    return x

def delete_node(T: dict, z: int):
    # 1. zが子を持たない場合
    parent = T[z].parent
    if (T[z].left is None) and (T[z].right is None):
        # zを削除
        if T[parent].left == z:
            T[parent].left = None
        elif T[parent].right == z:
            T[parent].right = None
        else:
            raise ValueError
        del T[z]
    
    # 2. zがちょうど1つの子を持つ場合
    elif T[z].right is None:
        # 左だけ子がある場合
        is_z_left = True if T[parent].left == z else False
        child = T[z].left
        if is_z_left: # zが、zの親の左側の子なら
            T[parent].left = child
        else: # zが、zの親の右側の子なら
            T[parent].right = child
        T[child].parent = parent
        del T[z]
    
    elif T[z].left is None:
        # 右だけ子がある場合
        is_z_left = True if T[parent].left == z else False
        child = T[z].right
        if is_z_left: # zが、zの親の左側の子なら
            T[parent].left = child
        else: # zが、zの親の右側の子なら
            T[parent].right = child
        T[child].parent = parent
        del T[z]
    
    elif (T[z].left is not None) and (T[z].right is not None):
        left, right = T[z].left, T[z].right
        # 指定したノードの子孫の中で最も小さいノードを返す
        node_next_more = get_min_descendants(T, T[z].right)
        next_more_right = T[node_next_more].right
        next_more_parent = T[node_next_more].parent
        # z がROOTだったら
        if parent is None:
            if node_next_more == right:
                T[right].parent = None
                T[right].left = left
                ROOT = right
                del T[z]
                return
            else:
                # node_next_moreがもっと下にある場合
                T[node_next_more].left = left
                T[node_next_more].right = right
                T[node_next_more].parent = None
                T[left].parent = node_next_more # zの左側の子の親
                T[right].parent = node_next_more # zの右側の子の親
                # node_next_moreの親 -> node_next_more右子の接続
                T[next_more_parent].left = next_more_right
                if next_more_right is not None:
                    T[next_more_right].parent = next_more_parent
                
                del T[z]
                return
        
        else: # zが非ROOTだったら
            is_z_left = True if T[parent].left == z else False
            if node_next_more == right:
                # zをつぶしてzの(元)親の子の枠のうち、もともとｚがいた方に、zの右子を繋げる
                if is_z_left:
                    T[parent].left = right
                else:
                    T[parent].right = right
                T[right].parent = parent
                T[right].left = left
                del T[z]
                return
            else:
                # zの親->next_more
                if is_z_left:
                    T[parent].left = node_next_more
                else:
                    T[parent].right = node_next_more
                # next_more -> z の子
                T[node_next_more].left = left
                T[node_next_more].right = right
                T[node_next_more].parent = parent
                T[left].parent = node_next_more # ｚの左の接続
                T[right].parent = node_next_more # zの右の接続
                # node_next_moreの親 -> node_next_more右子の接続
                # (node_next_moreの親から見ると左に接続される)
                # next_moreはzの親と子の間に繋ぎ変えたので、
                # next_more_parentとnext_more_rightを繋げる。
                T[next_more_parent].left = next_more_right
                if next_more_right is not None:
                    # next_moreの右子があるなら、next_moreの分だけ詰める
                    T[next_more_right].parent = next_more_parent
                
                del T[z]
                return

def get_min_descendants(T:dict, z:int):
    x = z
    while T[x].left is not None:
        x = T[x].left
    return x

def print_result(T: dict, ROOT: int):
    pre_ls, in_ls = [], []
    in_parse(T, ROOT, in_ls)
    pre_parse(T, ROOT, pre_ls)
    print("", *in_ls)
    print("", *pre_ls)

def main():
    N = int(input())
    T = {}
    ROOT = 0
    for i in range(N):
        tmp = input().split()
        if tmp[0] == "insert":
            value = int(tmp[1])
            if i==0:
                ROOT = value
            insert(T, ROOT, value)
        elif tmp[0] == "find":
            value = int(tmp[1])
            if find(T, ROOT, value):
                print("yes")
            else:
                print("no")
        elif tmp[0] == "delete":
            value = int(tmp[1])
            delete_node(T, value)
        else:
            print_result(T, ROOT)

main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2**20)#再帰回数上限の向上

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

def pre_parse(T:dict, u: int, pre_lis: list):
    if u == None:
        return
    pre_lis.append(u)
    pre_parse(T, T[u].left, pre_lis)
    pre_parse(T, T[u].right, pre_lis)

def in_parse(T,u,in_lis):
    if u == None:
        return
    in_parse(T, T[u].left, in_lis)
    in_lis.append(u)
    in_parse(T, T[u].right, in_lis)

def insert(T, Root, z):
    #zは接点番号（そして接点番号が内容でもある）
    #この接点番号を二分探索木の条件に従うように挿入する
    #もしＴが空なら
    if Root == z:
        T[z] = Node()
    #もしTにいくつか入っていた場合
    else:
        T[z] = Node()#初期化
        x = Root
        while x is not None:
            #子供がNoneになったらbreakする。next_parentが挿入するものの親
            next_parent = x
            if x > z:
                x = T[x].left
                temp = 1
            else:
                x = T[x].right
                temp = 2

        T[z].parent = next_parent
        if temp == 1:
            T[next_parent].left = z
        else:
            T[next_parent].right = z

def find(T,Root,k):
    #Tからkを見つけ出す。ひたすらkの大きさによって左右のパスをたどっていくだけ。
    x = Root
    while x != None and x != k:
        if k < x:
            x = T[x].left
        else:
            x = T[x].right
    return x

def delete_node(T,z):
    # case1指定したzが子を持たないとき
    parent = T[z].parent
    if (T[z].left is None) and (T[z].right is None):
        #そのノードを消去する
        if T[parent].left == z:
            T[parent].left = None
        elif T[parent].right == z:
            T[parent].right = None
        else:
            raise ValueError("something wrong in case 1")

        del T[z]

    #case2 指定した子が一つの子を持つ場合
    elif T[z].right is None:
        #左の子だけある場合、左の子ノードを親に繋ぐ
        #親の左右どちらかにつけるかはzの繋がり方に依存する。
        z_is_left = True if T[parent].left == z else False
        child = T[z].left
        if z_is_left:
            T[parent].left = child
            T[child].parent = parent
            del T[z]
        else:
            T[parent].right = child
            T[child].parent = parent
            del T[z]

    elif T[z].left is None:
        z_is_left = True if T[parent].left == z else False
        child = T[z].right
        if z_is_left:
            T[parent].left = child
        else:
            T[parent].right = child
        T[child].parent = parent
        del T[z]

    #case3 zが二つの子を持つ場合
    elif (T[z].left is not None) and (T[z].right is not None):
        left, right = T[z].left, T[z].right
        #指定したノードの右部分木の中の子孫の中で最も小さいノードをもらう
        node_next_more = get_min_in_descendants(T,T[z].right)
        next_more_right = T[node_next_more].right
        next_more_parent = T[node_next_more].parent
        #zがRootなら
        if parent is None:
            if node_next_more == right:
                #node_next_moreがrightの場合
                T[right].parent = None
                T[right].left = left
                Root = right
                del T[z]
                return

            else:
                #node_next_moreがもっと下流に存在する場合
                #zの子と親の接続
                T[node_next_more].left = left
                T[node_next_more].right = right
                T[node_next_more].parent = None
                T[left].parent = node_next_more
                T[right].parent = node_next_more
                if next_more_right is not None:
                    T[next_more_right].parent = next_more_parent
                    T[next_more_parent].left = next_more_right
                Root = node_next_more
                del T[z]
                return

        else:
            #zが非Root
            #zが親から見てどっち側についているか
            z_is_left = True if T[parent].left == z else False
            if node_next_more == right:
                if z_is_left:
                    T[parent].left = node_next_more
                else:
                    T[parent].right = node_next_more

                T[node_next_more].parent = parent
                T[node_next_more].left = left
                del T[z]
                return
            else:
                #zの親とnext_moreの接続
                if z_is_left:
                    T[parent].left = node_next_more
                else:
                    T[parent].right = node_next_more

                #next_moreと子供との接続
                T[node_next_more].left = T[z].left
                T[node_next_more].right = T[z].right
                T[node_next_more].parent = parent
                T[left].parent = node_next_more
                T[right].parent = node_next_more

                T[next_more_parent].left = next_more_right
                if next_more_right is not None:
                    T[next_more_right].parent = next_more_parent

                del T[z]
                return

def get_min_in_descendants(T,z):
    x = z
    while T[x].left is not None:
        x = T[x].left

    return x

def print_result(T):
    pre_ls = []
    in_ls = []
    in_parse(T,Root,in_ls)
    pre_parse(T,Root,pre_ls)
    print('', *in_ls)
    print('', *pre_ls)

N = int(input())
T = {}
for i in range(N):
    tmp = input()
    if tmp.startswith('print'):
        print_result(T)
    elif tmp.startswith('insert'):
        z = int(tmp.split()[1])
        if i == 0:
            Root = z
        insert(T,Root,z)
    elif tmp.startswith('find'):
        z = int(tmp.split()[1])
        if find(T,Root,z) is None:
            print('no')
        else:
            print('yes')
    elif tmp.startswith('delete'):
        z = int(tmp.split()[1])
        delete_node(T,z)