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: err = 2 * (10**9) + 1
  
  
  class STNode:
      def __init__(self, k, l, r, p):
          self.key = k
          self.left = l
          self.right = r
          self.parent = p
  
  
  def STinsert(h, z):
      global err
      p = None
      while True:
          if h.key == err:
              break
          p = h
          if z.key < h.key:
              h = h.left
          else:
              h = h.right
      if z.key < p.key:
          p.left = z
      else:
          p.right = z
      z.parent = p
  
  
  def STsearch(h, k):
      global err
      while h.key != err:
          if k < h.key:
              h = h.left
          elif h.key < k:
              h = h.right
          else:
              return h
      return None
  
  
  def STdelete(head, k):
      global err
      h = STsearch(head, k)
      if h is None:
          pass
      else:
          if h.left.key == err and h.right.key == err:
              if k < h.parent.key:  # h.leftはNULLnode
                  h.parent.left = h.left
              else:
                  h.parent.right = h.left
          elif h.left.key == err:  # right child exists
              h.right.parent = h.parent
              if k < h.parent.key:  # h.leftはNULLnode
                  h.parent.left = h.right
              else:
                  h.parent.right = h.right
          elif h.right.key == err:  # left child exists
              h.left.parent = h.parent
              if k < h.parent.key:  # h.rightはNULLnode
                  h.parent.left = h.left
              else:
                  h.parent.right = h.left
          else:
              # 一度右の子に移りそこから限界まで左の子を見る
              # 左の子がNULLnodeならループを抜ける
              # その節点の子が0個か1個かにより処理を分ける
              temp = h.right
              flg = 0  # 一度でもwhile内部で左の子に移動したら1
              while temp.left.key != err:
                  temp = temp.left
                  flg = 1
  
              # tempは中間順でhの次節点を参照する
              h.key = temp.key
              if temp.right.key == err:
                  if flg == 1:
                      temp.parent.left = temp.left
                  else:
                      temp.parent.right = temp.left
              else:
                  temp.right.parent = temp.parent
                  if flg == 1:
                      temp.parent.left = temp.right
                  else:
                      temp.parent.right = temp.right
  
  
  def preorder(head, h, A):
      global err
      if h.key == err:
          return
      A.append(h.key)
      preorder(head, h.left, A)
      preorder(head, h.right, A)
      if head == h:
          print("", *A)
  
  
  def inorder(head, h, B):
      global err
      if h.key == err:
          return
      inorder(head, h.left, B)
      B.append(h.key)
      inorder(head, h.right, B)
      if head == h:
          print("", *B)
  
  
  n = int(input())
  NULLnode = STNode(err, None, None, None)
  
  first = list(input().split())
  head = STNode(int(first[1]), NULLnode, NULLnode, NULLnode)
  
  for i in range(n - 1):
      temp = list(input().split())
      if temp[0] == "insert":
          z = STNode(int(temp[1]), NULLnode, NULLnode, NULLnode)
          STinsert(head, z)
      elif temp[0] == "print":
          A = []
          B = []
          inorder(head, head, B)
          preorder(head, head, A)
      elif temp[0] == "find":
          res = STsearch(head, int(temp[1]))
          if res is None:
              print("no")
          else:
              print("yes")
      else:  # delete
          STdelete(head, int(temp[1]))
  
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"}]