output_description: 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_
input_description: 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.
attempt: # -*- coding: utf-8 -*-
  """
  Created on Sat Mar  2 17:11:49 2019
  
  @author: Yamazaki Kenichi
  """
  
  m = int(input())
  A = [list(input().split()) for i in range(m)]
  
  T = [[-1, -1, -1, -1]]
  
  
  def insert(T, u, x):
      if T[0][3] == -1:
          T[0][3] = x
          return
      if x < T[u][3]:
          if T[u][1] == -1:
              T[u][1] = len(T)
              T.append([u, -1, -1, x])
          else:
              insert(T, T[u][1], x)
      else:
          if T[u][2] == -1:
              T[u][2] = len(T)
              T.append([u, -1, -1, x])
          else:
              insert(T, T[u][2], x)
  
  
  def ino(u):
      if T[u][1] != -1:
          ino(T[u][1])
      ino_res.append(str(T[u][3]))
      if T[u][2] != -1:
          ino(T[u][2])
  
  
  def pre(u):
      pre_res.append(str(T[u][3]))
      if T[u][1] != -1:
          pre(T[u][1])
      if T[u][2] != -1:
          pre(T[u][2])
  
  
  def find(u, x):
      if x == T[u][3]:
          return True
      elif x < T[u][3]:
          if T[u][1] == -1:
              return False
          return find(T[u][1], x)
      else:
          if T[u][2] == -1:
              return False
          return find(T[u][2], x)
  
  
  def dele(u, x):
      if T[u][1] == -1 and T[u][2] == -1:
          if T[T[u][0]][1] == u:
              T[T[u][0]][1] = -1
          else:
              T[T[u][0]][2] = -1
      elif T[u][1] != -1 and T[u][2] != -1:
          T[u][3] = T[T[u][0]][3]
          if T[T[u][0]][1] == u:
              T[T[u][0]][1] = -1
          else:
              T[T[u][0]][2] = -1
          dele(T[u][0])
      elif T[u][1] != -1:
          if T[T[u][0]][1] == u:
              T[T[u][0]][1] = T[u][1]
              T[T[u][1]][0] = T[u][0]
          else:
              T[T[u][0]][2] = T[u][1]
              T[T[u][2]][0] = T[u][0]
      elif T[u][2] != -1:
          if T[T[u][0]][1] == u:
              T[T[u][0]][1] = T[u][2]
              T[T[u][1]][0] = T[u][0]
          else:
              T[T[u][0]][2] = T[u][2]
              T[T[u][2]][0] = T[u][0]
  
  
  def delete(u, x):
      if x == T[u][3]:
          dele(u, x)
      elif x < T[u][3]:
          delete(T[u][1], x)
      else:
          delete(T[u][2], x)
  
  
  for c in A:
      if c[0] == "insert":
          insert(T, 0, int(c[1]))
      elif c[0] == "find":
          print("yes") if find(0, int(c[1])) else print("no")
      elif c[0] == "delete":
          delete(0, int(c[1]))
      else:
          ino_res = []
          ino(0)
          pre_res = []
          pre(0)
          print(" " + " ".join(ino_res))
          print(" " + " ".join(pre_res))
  
problem_description: 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:
  
    1. If $z$ has no children, we modify its parent $z.p$ to replace $z$ with NIL as its child (delete $z$).
    2. If $z$ has only a single child, we "splice out" $z$ by making a new link between its child and its parent.
    3. If $z$ has two children, we splice out $z$'s successor $y$ and replace $z$'s key with $y$'s key.
samples: [{"input": "18\n    insert 8\n    insert 2\n    insert 3\n    insert 7\n    insert 22\n    insert 1\n    find 1\n    find 2\n    find 3\n    find 4\n    find 5\n    find 6\n    find 7\n    find 8\n    print\n    delete 3\n    delete 7\n    print", "output": "yes\n    yes\n    yes\n    no\n    no\n    no\n    yes\n    yes\n     1 2 3 7 8 22\n     8 2 1 3 7 22\n     1 2 8 22\n     8 2 1 22"}]