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.

Solution (Python):



def insert(root, insert_node):
    focus_node = root
    parent = None
    while not focus_node == None:
        parent = focus_node
        if focus_node["data"]  > insert_node["data"]:
            focus_node = focus_node["left"]
        else:
            focus_node = focus_node["right"]

    if parent["data"] > insert_node["data"]:
        parent["left"] = insert_node
        insert_node["parent"] = parent
    else:
        parent["right"] = insert_node
        insert_node["parent"] = parent

def get_preorder(node):
    if node == None:
        return []
    r = []
    r.append(str(node["data"]))
    r.extend(get_preorder(node["left"]))
    r.extend(get_preorder(node["right"]))

    return r
    
def get_inorder(node):
    if node == None:
        return []
    r = []
    r.extend(get_inorder(node["left"]))
    r.append(str(node["data"]))
    r.extend(get_inorder(node["right"]))

    return r

def delete_tree(root, target):
    
    delete_node = find_tree(root, target)
    parent = delete_node["parent"]
    if parent["left"] == delete_node:
        parent_direction = "left"
    else:
        parent_direction = "right"
    
    while True:
        if delete_node["left"] == None and delete_node["right"] == None:
            parent[parent_direction] = None
            break
        elif delete_node["left"] and delete_node["right"]:
            p = get_inorder(root)
            next_num = int(p[p.index(str(delete_node["data"])) + 1])
            tmp_delete_node = find_tree(root, next_num)
            delete_node["data"] = next_num
            delete_node = tmp_delete_node
            parent = delete_node["parent"]
            if parent == None:
                parent_direction = None
            elif parent["left"] == delete_node:
                parent_direction = "left"
            else:
                parent_direction = "right"
        else:
            if delete_node["left"]:
                parent[parent_direction] = delete_node["left"]
                delete_node["left"]["parent"] = parent
            else:
                parent[parent_direction] = delete_node["right"]
                delete_node["right"]["parent"] = parent
            break

    
def find_tree(root, target):
    focus_node = root

    while not focus_node == None:
        if focus_node["data"] == target:
            return focus_node
        elif focus_node["data"] < target:
            focus_node = focus_node["right"]
        else:
            focus_node = focus_node["left"]
    
    return None
    
def print_tree(root):
    print(" " + " ".join(get_inorder(root)))
    print(" " + " ".join(get_preorder(root)))
    
def main():
    
    n_line = int(input())
    input_list = [input() for i in range(n_line)]
    root = {"left":None, "right": None, "data":int(input_list[0].split()[1]), "parent": None}

    for line in input_list[1:]:
        if line == "print":
            print_tree(root)
        else:
            split_line = line.split()
            if split_line[0] == "insert":
                node = {"left":None, "right": None, "data":int(split_line[1]), "parent":None}
                insert(root, node)
            elif split_line[0] == "find":
                if find_tree(root, int(split_line[1])):
                    print("yes")
                else:
                    print("no")
            elif split_line[0] == "delete":
                delete_tree(root, int(split_line[1]))
        
        

if __name__ == "__main__":
    main()

Solution (Python):



def insert(root, insert_node):
    focus_node = root
    parent = None
    while not focus_node == None:
        parent = focus_node
        if focus_node["data"]  > insert_node["data"]:
            focus_node = focus_node["left"]
        else:
            focus_node = focus_node["right"]

    if parent["data"] > insert_node["data"]:
        parent["left"] = insert_node
        insert_node["parent"] = parent
    else:
        parent["right"] = insert_node
        insert_node["parent"] = parent

def get_preorder(node):
    if node == None:
        return []
    r = []
    r.append(str(node["data"]))
    r.extend(get_preorder(node["left"]))
    r.extend(get_preorder(node["right"]))

    return r
    
def get_inorder(node):
    if node == None:
        return []
    r = []
    r.extend(get_inorder(node["left"]))
    r.append(str(node["data"]))
    r.extend(get_inorder(node["right"]))

    return r

def delete_tree(root, target):
    
    delete_node = find_tree(root, target)
    parent = delete_node["parent"]
    if parent["left"] == delete_node:
        parent_direction = "left"
    else:
        parent_direction = "right"
    
    while True:
        if delete_node["left"] == None and delete_node["right"] == None:
            parent[parent_direction] = None
            break
        elif delete_node["left"] and delete_node["right"]:
            p = get_inorder(root)
            next_num = int(p[p.index(str(delete_node["data"])) + 1])
            tmp_delete_node = find_tree(root, next_num)
            delete_node["data"] = next_num
            delete_node = tmp_delete_node
            parent = delete_node["parent"]
            if parent == None:
                parent_direction = None
            elif parent["left"] == delete_node:
                parent_direction = "left"
            else:
                parent_direction = "right"
        else:
            if delete_node["left"]:
                parent[parent_direction] = delete_node["left"]
                delete_node["left"]["parent"] = parent
            else:
                parent[parent_direction] = delete_node["right"]
                delete_node["right"]["parent"] = parent
            break

    
def find_tree(root, target):
    focus_node = root

    while not focus_node == None:
        if focus_node["data"] == target:
            return focus_node
        elif focus_node["data"] < target:
            focus_node = focus_node["right"]
        else:
            focus_node = focus_node["left"]
    
    return None
    
def print_tree(root):
    print(" " + " ".join(get_inorder(root)))
    print(" " + " ".join(get_preorder(root)))
    
def main():
    
    n_line = int(input())
    input_list = [input() for i in range(n_line)]
    root = {"left":None, "right": None, "data":int(input_list[0].split()[1]), "parent": None}

    for line in input_list[1:]:
        if line == "print":
            print_tree(root)
        else:
            split_line = line.split()
            target = int(split_line[1])
            if split_line[0] == "insert":
                node = {"left":None, "right": None, "data":int(split_line[1]), "parent":None}
                insert(root, node)
            elif split_line[0] == "find":
                if find_tree(root, target):
                    print("yes")
                else:
                    print("no")
            elif split_line[0] == "delete":
                delete_tree(root, target)
        
        

if __name__ == "__main__":
    main()

Solution (Python):
class Node(object):
    root = None

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

    @classmethod
    def insert(cls, z):
        y = None
        x = cls.root
        while x != None:  
            y = x
            if z.key < x.key:
                x = x.left
            else:
                x = x.right
        
        z.parent = y
        if y == None:
            cls.root = z
        elif z.key < y.key:
            y.left = z
        else:
            y.right = z
        

    @classmethod
    def find(cls, k):
        """ ??????k?????????????????¢?????????????????????????????°None????????? """
        x = cls.root
        while x != None and k != x.key:
            if k < x.key:
                x = x.left
            else:
                x = x.right
        return x

    @classmethod
    def walk_preorder(cls, node):
        """ ??????????????? """
        
        
        print(' {0}'.format(node.key), end='')
        if node.left != None:
            
            cls.walk_preorder(node.left)
        if node.right != None:
            
            cls.walk_preorder(node.right)
        

    @classmethod
    def walk_inorder(cls, node):
        """ ??????????????? """
        
        if node.left != None:
            
            cls.walk_inorder(node.left)
        
        print(' {0}'.format(node.key), end='')
        if node.right != None:
            
            cls.walk_inorder(node.right)
        

    @classmethod
    def delete_node(cls, z):
        if z.left == None or z.right == None:
            y = z
        else:
            y = Node.get_successor(z)
        if y.left != None:
            x = y.left
        else:
            x = y.right
        if x != None:
            x.parent = y.parent
        if y.parent == None:
            Node.root = x
        elif y == y.parent.left:
            y.parent.left = x
        else:
            y.parent.right = x
        if y != z:
            z.key = y.key

    @classmethod
    def get_successor(cls, x):
        if x.right != None:
            return Node.get_minimum(x.right)
        y = x.parent
        while y != None and x == y.right:
            x = yy = y.parent
        return y

    @classmethod
    def get_minimum(cls, x):
        """ ??????x????????¨????????¨?????¨????????§????°?????????????????????????????????? """
        while x.left != None:
            x = x.left
        return x

    def get_type(self):
        if self.parent == None:
            return 'root'
        elif self.left == None and self.right == None:
            return 'leaf'
        else:
            return 'internal node'

    def get_depth(self):
        if self.parent == None:
            return 0
        else:
            depth = 1
            t = self.parent
            while t.parent != None:
                t = t.parent
                depth += 1
            return depth

    def get_height(self):
        if self.height:
            return self.height
        h_left = 0
        h_right = 0
        if self.left != None:
            h_left = self.left.get_height() + 1
        if self.right != None:
            h_right = self.right.get_height() + 1
        self.height = max(h_left, h_right)
        return self.height

    def get_degree(self):
        degree = 0
        if self.left != None:
            degree += 1
        if self.right != None:
            degree += 1
        return degree

    def get_sibling(self):
        if self.parent == None:
            return -1
        p = self.parent
        if p.left != self and p.left != None:
            return p.left
        if p.right != self and p.right != None:
            return p.right


def process_node_data(node_data):
    for inst in node_data:
        if inst[0] == 'print':
            result = Node.walk_inorder(Node.root)
            print('')
            
            result = Node.walk_preorder(Node.root)
            
            print('')
        elif inst[0] == 'insert':
            node_key = int(inst[1])
            new_node = Node(node_key)
            Node.insert(new_node)
        elif inst[0] == 'find':
            result = Node.find(int(inst[1]))
            if result:
                print('yes')
            else:
                print('no')
        elif inst[0] == 'delete':
            result = Node.delete_node(Node.find(int(inst[1])))



def flatten(l):
    """ http://stackoverflow.com/questions/2158395/flatten-an-irregular-list-of-lists-in-python """
    import collections
    for el in l:
        if isinstance(el, collections.Iterable) and not isinstance(el, (str, bytes)):
            yield from flatten(el)
        else:
            yield el


if __name__ == '__main__':
    
    num_of_nodes = int(input())
    node_data = [input().split(' ') for _ in range(num_of_nodes)]
    
    
    
    
    
    
    

    
    
    process_node_data(node_data)

Solution (Python):
import sys
 
NIL = -1
 
class Node:
    def __init__(self, key):
        self.key = key
        self.parent = NIL
        self.left = NIL
        self.right = NIL
 
class Tree:
    def __init__(self):
        self.root = NIL
 
    def insert(self, z):
        y = NIL
        x = self.root
 
        while x != NIL:
            y = x
 
            if z.key < x.key:
                x = x.left
            else:
                x = x.right
 
        z.parent = y
 
        if y == NIL:
            self.root = z
        elif z.key < y.key:
            y.left = z
        else:
            y.right = z

    def find(self, value, node):
        if node == NIL:
            return False
        elif node.key == value:
            return True
        elif value < node.key:
            
            return self.find(value, node=node.left)
        else:
            
            return self.find(value, node=node.right)

    def delete(self, value, node):
        if node == NIL:
            return None
        elif value < node.key:
            self.delete(value, node.left)
        elif value > node.key:
            self.delete(value, node.right)
        else:
            check = (node.left != NIL) + (node.right != NIL)

            if check == 0:
                if node.parent.left != NIL and node.parent.left.key == value:
                    node.parent.left = NIL
                else:
                    node.parent.right = NIL

            elif check == 1:
                if node.left != NIL:
                    child = node.left
                else:
                    child = node.right

                if node.parent.left != NIL and node.parent.left.key == value:
                    node.parent.left = child
                    child.parent = node.parent
                else:
                    node.parent.right = child
                    child.parent = node.parent

            else:
                jisetu = node.right

                while jisetu.left != NIL:
                    jisetu = jisetu.left

                node.key = jisetu.key
                self.delete(jisetu.key, jisetu)

    def inorder_walk(self, node):
        if node == NIL:
            return None
 
        if node.left != NIL:
            self.inorder_walk(node=node.left)
 
        print(' ' + str(node.key), end='')
 
        if node.right != NIL:
            self.inorder_walk(node=node.right)
 
    def preorder_walk(self, node):
        if node == NIL:
            return None
 
        print(' ' + str(node.key), end='')
 
        if node.left != NIL:
            self.preorder_walk(node=node.left)
 
        if node.right != NIL:
            self.preorder_walk(node=node.right)
 
    def show(self):
        self.inorder_walk(self.root)
        print()
        self.preorder_walk(self.root)
        print()
 
 
n = int(sys.stdin.readline())
T = Tree()
 
for i in range(n):
    line = sys.stdin.readline().split()

    if len(line) == 1:
        T.show()
    elif line[0] == 'insert':
        key = int(line[1])
        T.insert(Node(key))
    elif line[0] == 'find':
        key = int(line[1])
        print('yes' if T.find(key, T.root) else 'no')
    else:
        key = int(line[1])
        T.delete(key, T.root)

Solution (Python):
import sys

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

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

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

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

    def insert(self, key):
        Nz = Node(key)
        Ny = None  
        Nx = self.root
        while Nx:
            Ny = Nx
            if Nz.key < Ny.key:
                Nx = Nx.left
            else:
                Nx = Nx.right
        Nz.parent = Ny
        if Ny == None:
            self.root = Nz
        elif Nz.key < Ny.key:
            Ny.left = Nz
        else:
            Ny.right = Nz

    def find(self, key):
        Nx = self.root
        while Nx and Nx.key != key:
            if key < Nx.key:
                Nx = Nx.left
            else:
                Nx = Nx.right
        return Nx

    def delete(self, key):
        Nz = self.find(key)
        
        if Nz.left and Nz.right:
            Ny = self.successor(Nz)
        else:
            Ny = Nz
        
        if Ny.left:
            Nx = Ny.left
        else:
            Nx = Ny.right

        if Nx:
            Nx.parent = Ny.parent

        if Ny.parent == None:
            self.root = Nx
        elif Ny == Ny.parent.left:
            Ny.parent.left = Nx
        else:
            Ny.parent.right = Nx

        if Ny != Nz:
            Nz.key = Ny.key

    def successor(self, Nx):
        if Nx.right:
            return self.minimum(Nx.right)

        Ny = Nx.parent
        while Ny != None and Nx == Ny.right:
            Nx = Ny
            Ny = Ny.parent
        return Ny

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

    def print(self):
        print('', ' '.join(map(str, self.root.inwalk())))
        print('', ' '.join(map(str, self.root.prewalk())))

tree = Tree()

n = sys.stdin.readline()
for line in sys.stdin:
    if line[0] == 'i':
        tree.insert(int(line.split()[1]))
    elif line[0] == 'f':
        if tree.find(int(line.split()[1])):
            print('yes')
        else:
            print('no')
    elif line[0] == 'd':
        tree.delete(int(line.split()[1]))
    else:
        tree.print()

Solution (Python):


import random
import sys
import os


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

    def __str__(self):
        if self.root == None:
            return None
        else:
            return "TODO"

    def print_inorder(self):
        self.inorder_list = []
        self.__inorder(self.root)
        return self.inorder_list

    def __inorder(self, node):
        """
        :param node: Node
        :return:
        """
        if node is None:
            return
        else:
            self.__inorder(node.left)
            self.inorder_list.append(node.key)
            self.__inorder(node.right)

    def print_preorder(self):
        self.preorder_list = []
        self.__preorder(self.root)
        return self.preorder_list

    def __preorder(self, node):
        """
        :param node: Node
        :return:
        """
        if node is None:
            return
        else:
            self.preorder_list.append(node.key)
            self.__preorder(node.left)
            self.__preorder(node.right)

    def insert(self, node):
        """
        :param node: Node
        :return:
        """
        if self.root is None:
            self.root = node
        else:
            x = self.root
            parent_candidate = x

            while x is not None:
                parent_candidate = x
                if x.key > node.key:
                    x = x.left
                else:
                    x = x.right

            
            x = node
            x.parent = parent_candidate

            
            if x.key < x.parent.key:
                x.parent.left = x
            else:
                x.parent.right = x

    def find(self, value):
        """
        :param value:
        :rtype: Node
        :return:
        """
        x = self.root
        while x is not None and x.key != value:
            if x.key > value:
                x = x.left
            else:
                x = x.right
        return x

    def delete(self, value):
        found_node = self.find(value)
        if found_node is None:
            print("value is nothing")
        else:
            
            if found_node.is_leaf():
                
                
                

                if found_node.parent.left is not None and found_node.parent.left.key == found_node.key:
                    found_node.parent.left = None
                else:
                    found_node.parent.right = None
            else:
                
                if found_node.has_one_child():
                    one_child = found_node.get_one_child()

                    
                    one_child.parent = found_node.parent

                    
                    if found_node.parent.left == found_node:
                        found_node.parent.left = one_child
                    else:
                        found_node.parent.right = one_child

                
                else:
                    next_section_point = found_node.get_next_section_point()
                    
                    
                    key = next_section_point.key
                    self.delete(next_section_point.key)
                    found_node.key = key


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

    def has_one_child(self):
        if self.left is None and self.right is not None:
            return True
        elif self.left is not None and self.right is None:
            return True
        else:
            return False

    def get_one_child(self):
        if not self.has_one_child():
            return None
        else:
            if self.left is not None:
                return self.left
            else:
                return self.right

    def get_next_section_point(self):
        """?¬??????????????????????"""

        
        if self.right is not None:
            return self.right.get_minimum()
        
        else:
            
            return self.parent

    def is_leaf(self):
        if self.left is None and self.right is None:
            return True
        else:
            return False

    def get_minimum(self):
        if self.left is None:
            return self
        else:
            return self.left.get_minimum()

tree = Tree()
s = input()
n = int(s)
for _ in range(n):
    s = input()
    if 'insert' in s:
        value = int(s.split(" ")[-1])
        node = Node(value)
        tree.insert(node)

    if 'print' in s:
        in_list = tree.print_inorder()
        in_list = map(str, in_list)
        print(' ' + ' '.join(in_list))

        pre_list = tree.print_preorder()
        pre_list = map(str, pre_list)
        print(' ' + ' '.join(pre_list))

    if 'find' in s:
        value = int(s.split(" ")[-1])
        node = tree.find(value)
        if node is None:
            print('no')
        else:
            print('yes')

    if 'delete' in s:
        value = int(s.split(" ")[-1])
        tree.delete(value)

Solution (Python):
class Node:
  def __init__(self, num):
    self.key = num
    self.p = None
    self.left = None
    self.right = None

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

  def insert(self, z):
    y = None
    x = self.root
    while x != None:
      y = x
      if z.key < x.key:
        x = x.left
      else:
        x = x.right
    z.p = y

    if y is None:
      self.root = z
    elif z.key < y.key:
      y.left = z
    else:
      y.right = z

  def find(self, key):
    node = self.root
    while node:
      if node.key == key: return node
      if key < node.key:
        node = node.left
      else:
        node = node.right
    return None

  def find_minimum(self, node):
    while node.left: node = node.left
    return node

  def delete(self, node):
    if node.left and node.right:
      m = self.find_minimum(node.right)
      node.key = m.key
      self.delete(m)
    elif node.left:
      self.update(node, node.left)
    elif node.right:
      self.update(node, node.right)
    else:
      self.update(node, None)

  def update(self, node, new_node):
    if node.key < node.p.key:
      node.p.left = new_node
    else:
      node.p.right = new_node
    if new_node:
      new_node.p = node.p

def print_inorder(node):
  if node is None: return
  print_inorder(node.left)
  print(" {}".format(node.key), end="")
  print_inorder(node.right)

def print_preorder(node):
  if node is None: return
  print(" {}".format(node.key), end="")
  print_preorder(node.left)
  print_preorder(node.right)

T = BinarySearchTree()
for i in range(int(input())):
  params = input().split()
  if params[0] == "insert":
    T.insert(Node(int(params[1])))
  elif params[0] == "find":
    if T.find(int(params[1])):
      print("yes")
    else:
      print("no")
  elif params[0] == "delete":
    node = T.find(int(params[1]))
    if node: T.delete(node)
  elif params[0] == "print":
    print_inorder(T.root)
    print("")
    print_preorder(T.root)
    print("")

Solution (Python):
class Node:
  def __init__(self, num):
    self.key = num
    self.p = None
    self.left = None
    self.right = None

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

  def insert(self, z):
    y = None
    x = self.root
    while x != None:
      y = x
      if z.key < x.key:
        x = x.left
      else:
        x = x.right
    z.p = y

    if y is None:
      self.root = z
    elif z.key < y.key:
      y.left = z
    else:
      y.right = z

  def find(self, key):
    node = self.root
    while node:
      if node.key == key: return node
      if key < node.key:
        node = node.left
      else:
        node = node.right
    return None

  def find_minimum(self, node):
    while node.left: node = node.left
    return node

  def delete(self, node):
    if node.left and node.right:
      m = self.find_minimum(node.right)
      node.key = m.key
      self.delete(m)
    elif node.left:
      self.update(node, node.left)
    elif node.right:
      self.update(node, node.right)
    else:
      self.update(node, None)

  def update(self, node, new_node):
    if node.p is None:
      self.root = new_node
      if new_node: new_node.p = None
      return

    if node.key < node.p.key:
      node.p.left = new_node
    else:
      node.p.right = new_node
    if new_node:
      new_node.p = node.p

def print_inorder(node):
  if node is None: return
  print_inorder(node.left)
  print(" {}".format(node.key), end="")
  print_inorder(node.right)

def print_preorder(node):
  if node is None: return
  print(" {}".format(node.key), end="")
  print_preorder(node.left)
  print_preorder(node.right)

T = BinarySearchTree()
for i in range(int(input())):
  params = input().split()
  if params[0] == "insert":
    T.insert(Node(int(params[1])))
  elif params[0] == "find":
    if T.find(int(params[1])):
      print("yes")
    else:
      print("no")
  elif params[0] == "delete":
    node = T.find(int(params[1]))
    if node: T.delete(node)
  elif params[0] == "print":
    print_inorder(T.root)
    print("")
    print_preorder(T.root)
    print("")

Solution (Python):
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 is None:
            self.root = z
        elif z.key < y.key:
            y.left = z
        else:
            y.right = z

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

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

        y = x.parent
        while y 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

    def delete(self, key):
        
        z = self.find(key)
        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 show(self):
        print(" ", end="")
        print(*list(map(str, self.root.inwalk())))
        print(" ", end="")
        print(*list(map(str, self.root.prewalk())))


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

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

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


tree = Tree()
n = int(input())
for i in range(n):
    cmd = list(input().split())
    if cmd[0] == 'insert':
        tree.insert(int(cmd[1]))
    elif cmd[0] == 'find':
        if tree.find(int(cmd[1])):
            print("yes")
        else:
            print("no")
    elif cmd[0] == 'print':
        tree.show()
    elif cmd[0] == 'delete':
        tree.delete(int(cmd[1]))