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

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)
        #print(hoge)
        #print()

Submission status: Wrong Answer

Solution code:
class Tree():
    def __init__(self):
        self.root = None
    def insert(self, key):
        z = Node(key)
        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 == 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.inwalk())))
        print('', ' '.join(map(str, self.root.prewalk())))

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

    def delete(self, k):
        z = self.find(tree.root, k)
        y = self.minimum(z) if z.left and z.right else z
        x = y.left if y.left else y.right

        if x:
            x.parent = y.parent
        if y.parent == 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 minimum(self, x):
        while x.left:
            x = x.left
        return x

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

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

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

tree = Tree()
n = int(input())
for i in range(n):
    com = input().split()
    if com[0] == "insert":
        tree.insert(int(com[1]))
    elif com[0] == "find":
        ans = tree.find(tree.root, int(com[1]))
        if ans != None:
            print("yes")
        else:
            print("no")
    elif com[0] == "delete":
        tree.delete(int(com[1]))
    else:
        tree.print()

Submission status: Wrong Answer

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:
        tmp = x.left.value
        delete(x.left.value)
        x.value = tmp

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]))

Submission status: Wrong Answer

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 delete(id, root_node):
    # 作成中
    global null_node
    type = ''
    node = root_node
    node_parent = null_node
    while node.id != id:
        node_parent = node
        if id < node.id:
            node = node.left
            type = 'L'
        else:
            node = node.right
            type = 'R'
    if node.right is not None:
        node.right.parent = node_parent
        node = node.right
    elif node.left is not None:
        node.left.parent = node_parent
        node = node.left
    else:
        node.parent = null_node
        node = null_node

    if type == 'L':
        node_parent.left = node
    else:
        node_parent.right = 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: Wrong Answer

Solution code:
import time
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):
    if 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':
        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: Time Limit Exceeded

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

def inorder(n):
    if n != None:
        inorder(n.left)
        print n.v,
        inorder(n.right)

def preorder(n):
    if n != None:
        print n.v,
        preorder(n.left)
        preorder(n.right)

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

    def find(self,v):
        x = self.root
        while x != None:
            if x.v == v:
                return x
            elif x.v < v:
                x = x.right
            else:
                x = x.left
        return None

    def delete(self,v):
        x = self.root
        y = None
        while x != None:
            if x.v == v:
                break
            elif x.v < v:
                y = x
                x = x.right
            else:
                y = x
                x = x.left
        if x != None:
            if x.left != None and x.right != None:
                z = x.right
                w = x
                while z.left != None:
                    w = z
                    z = z.left
                x.v = z.v
                if w.left == z:
                    w.left = z.right
                else:
                    w.right = z.right
            else:
                z = x.left
                if z == None:
                    z = x.right
                if y.left == x:
                    y.left = z
                else:
                    y.right = z


    def insert(self,v):
        n = Node(v)
        x = self.root
        y = None
        while x != None:
            y = x
            if x.v > v:
                x = x.left
            else:
                x = x.right
        if y == None:
            self.root = n
        else:
            if y.v > v:
                y.left = n
            else:
                y.right = n
    def print_tree(self):
        print '',
        inorder(self.root)
        print
        print '',
        preorder(self.root)
        print


n = int(raw_input())
ops = []
for _ in range(n):
    ops.append(raw_input())

tree = BST()
for op in ops:
    if op[0] == 'i':
        num = op.split(' ')[1]
        num = int(num)
        tree.insert(num)
    elif op[0] == 'f':
        num = op.split(' ')[1]
        num = int(num)
        if tree.find(num):
            print 'yes'
        else:
            print 'no'
    elif op[0] == 'd':
        num = op.split(' ')[1]
        num = int(num)
        tree.delete(num)
    else:
        tree.print_tree()

Submission status: Time Limit Exceeded

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

class BinaryTree:
  def __init__(self):
    self.root = Node(None)

  def insert_node(self, node, n):
    if node.label == None:
      node.label = n
    elif n < node.label:
      if node.left == None:
        node.left = Node(n)
      else:
        node.left = self.insert_node(node.left, n)
    else:
      if node.right == None:
        node.right = Node(n)
      else:
        node.right = self.insert_node(node.right, n)
    return node

  def node_printer(self, node):
    labels = []
    if node.left != None:
      labels.extend(self.node_printer(node.left))
    labels.append(node.label)
    if node.right != None:
      labels.extend(self.node_printer(node.right))
    return labels

  def node_printer_c(self, node):
    labels = []
    labels.append(node.label)
    if node.left != None:
      labels.extend(self.node_printer_c(node.left))
    if node.right != None:
      labels.extend(self.node_printer_c(node.right))
    return labels

  def find_node(self, node, x):
    if node == None:
      return False
    elif node.label == x:
      return True
    elif x < node.label:
      return self.find_node(node.left, x)
    elif node.label < x:
      return self.find_node(node.right, x)

  def find_minimum_node(self, node):
    if node.label == None:
      return -1
    elif node.left == None:
      return node.label
    else:
      return self.find_minimum_node(node.left)

  def delete_node(self, node, x):
    if node.label == None:
      return node
    elif node.label == x:
     if node.left == None and node.right == None:
       return None
     elif node.left != None and node.right != None:
       minnode = self.find_minimum_node(node.right)
       node.label = minnode
       node.right = self.delete_node(node.right, minnode)
     else:
       if node.left != None:
         return node.left
       else:
         return node.right
    elif x < node.label:
      node.left = self.delete_node(node.left, x)
    else:
      node.right = self.delete_node(node.right, x)
    return node

  # functions
  def insert(self, x):
    return self.insert_node(self.root, x)
  def printer(self):
    return self.node_printer(self.root)
  def printer_c(self):
    return self.node_printer_c(self.root)
  def find(self, x):
    return self.find_node(self.root, x)
  def delete(self, x):
    return self.delete_node(self.root, x)

btree = BinaryTree()
n = int(raw_input())
for _ in xrange(n):
  op = raw_input().split()
  if op[0] == "insert":
    btree.insert(int(op[1]))
  elif op[0] == "print":
    print " "+" ".join(map(str, btree.printer()))
    print " "+" ".join(map(str, btree.printer_c()))
  elif op[0] == "find":
    judge = btree.find(int(op[1]))
    if judge:
      print "yes"
    else:
      print "no"
  elif op[0] == "delete":
    btree.delete(int(op[1]))

Submission status: Time Limit Exceeded

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

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

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

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

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

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

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

Submission status: Time Limit Exceeded

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

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

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

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

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

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

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