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):
class Node(object):
    def __init__(self):
        self.left = None
        self.right = None
        self.value = None
        self.parent = None

class Tree(object):
    def __init__(self):
        self.root = None
        self.value_dic = {}
    
    def is_find(self,value):
        if value in self.value_dic:
            return True
        else:
            return False
    
    def find(self,value):
        node = T.root

        while node :
            if value == node.value:
                break
            elif value > node.value:
                node = node.right
            else :
                node = node.left
        return node

def insert(T,z):
    y = None
    x = T.root
    while x != None:
        y = x
        if z.value < x.value:
            x = x.left
        else:
            x = x.right
    
    z.parent = y
    if y == None:
        T.root = z
    elif z.value < y.value:
        y.left = z
    else :
        y.right = z

    T.value_dic[z.value] = 1

def getMinimum(z):
    while z.left != None:
        z = z.left
    return z

def getSuccessor(z):
    if z.right != None:
        return getMinimum(z.right)

    y = z.parent
    while y != None and z == y.right:
        z = y
        y = y.parent
    return y

def delete(T,z):
    
    if z.left is None or z.right is None:
        y = z
    else:
        y = getSuccessor(z)

    
    if y.left != None:
        x = y.left
    else:
        x = y.right
    

    
    if x != None:
        x.parent = y.parent
    
    if y.parent is None:
        T.root = x
    elif y.parent.left == y:
        y.parent.left = x
    else:
        y.parent.right = x
    
    if y != z:
        z.value = y.value




def preorder(node):
    if node is None:
        return 
    print(" "+str(node.value),end="")    
    preorder(node.left)
    preorder(node.right)
    

def inorder(node):
    if node is None:
        return 
    inorder(node.left)
    print(" "+str(node.value),end="")
    inorder(node.right)
    
def print_all_node(root):
    stack = [root]
    while stack:
        node = stack.pop()
        print("p: ",node.parent,"r:",node.right,"l:",node.left)
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)

if __name__ == "__main__":
    n = int(input())
    T = Tree()
    queries = [input().split() for _ in range(n)]
    for query in queries:
        if query[0] == "print":
            
            inorder(T.root)
            print("")
            preorder(T.root)
            print("")

        else:
            command,value = query
            if command == "insert":
                node_z = Node()
                node_z.value = int(value)
                insert(T,node_z)
            elif command == "find":
                if T.is_find(int(value)):
                    print("yes")
                else:
                    print("no")
            elif command == "delete":
                node = T.find(int(value))
                if node:
                    T.value_dic.pop(int(value))
                delete(T,node)

Solution (Python):


import sys
sys.setrecursionlimit(10**6)


class Node():
    __slots__ = ['key', 'parent', 'left', 'right']

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

    def __repr__(self):
        k = str(self.key)
        p = str(self.parent.key) if self.parent else 'None'
        l = str(self.left.key) if self.left else 'None'
        r = str(self.right.key) if self.right else 'None'
        s = "<Node %s: parent=%s, left=%s, right=%s>" % (k, p, l, r)
        return s


class BinaryTree():
    def __init__(self, n=0):
        self.T = [Node() for _ in range(n)]
        self.root = None

    def preorder(self):
        self.preorder_key = []
        self.preorder_rec(self.root)
        print('', *(self.preorder_key))

    def preorder_rec(self, node):
        if node == None:
            return
        self.preorder_key.append(node.key)
        self.preorder_rec(node.left)
        self.preorder_rec(node.right)

    def inorder(self):
        self.inorder_key = []
        self.inorder_rec(self.root)
        print('', *(self.inorder_key))

    def inorder_rec(self, node):
        if node == None:
            return
        self.inorder_rec(node.left)
        self.inorder_key.append(node.key)
        self.inorder_rec(node.right)

    def insert(self, key):
        node = Node(key)

        y = None
        x = self.root

        while x != None:
            y = x
            if key < x.key:
                x = x.left
            else:
                x = x.right

        node.parent = y
        if y == None:
            self.root = node
        elif key < y.key:
            y.left = node
        else:
            y.right = node

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

    def has(self, key):
        if self.find(self.root, key) != None:
            return True
        else:
            return False

    def get_successor(self, x):
        
        if x.right != None:
            return self.get_minimum(x.right)

        y = x.parent
        while y != None and x == y.right:
            x, y = y, y.parent
        return y

    def get_minimum(self, x):
        
        while x.left != None:
            x = x.left
        return x

    def delete(self, key):
        
        z = self.find(self.root, key)
        if z.left != None and z.right != None:
            y = self.get_successor(z)
            z.key = y.key
        else:
            y = z

        
        x = y.left if y.left != None else y.right
        if x != None:
            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


N = int(input())
S = [input() for _ in range(N)]
tree = BinaryTree()

for s in S:
    if 'print' in s:
        tree.inorder()
        tree.preorder()
    else:
        command, key = s.split()
        key = int(key)

        if 'find' in command:
            print('yes' if tree.has(key) else 'no')

        if 'delete' in command:
            tree.delete(key)

        elif 'insert' in command:
            tree.insert(key)

Solution (Python):
import sys
n = int(input())
class Node:
  def __init__(self,v):
    self.p = None
    self.key = v
    self.left = None
    self.right = None

sys.setrecursionlimit(15000)
r = None
def insert(z):
  global r
  y = None
  x = r
  while x != None:
    y = x
    if z.key < x.key:
      x = x.left
    else:
      x = x.right
  z.p = y

  if y == None:
    r = z
  elif z.key < y.key:
    y.left = z
  else:
    y.right = z

ret = []
def inorder(r):
  if r == None: return
  inorder(r.left)
  ret.append(r.key)
  inorder(r.right)

def preorder(r):
  if r == None: return
  ret.append(r.key)
  preorder(r.left)
  preorder(r.right)

def search(r,key):
  if r == None: return None
  if r.key == key:
    return r
  if r.key < key:
    return search(r.right,key)
  else:
    return search(r.left,key)

def delete(key):
  global r
  z = search(r,key)
  if not z.left or not z.right:
    y = z 
  else:
    y = z.right
    while y.left:
      y = y.left

  if y.left:
    x = y.left 
  else:
    x = y.right

  if x:
    x.p = y.p

  if y.p == None:
    r = x
  elif y == y.p.left:
    y.p.left = x
  else:
    y.p.right = x

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

for i in range(n):
  s = input()
  
  if s[0]=="i":
    insert(Node(int(s.split()[1])))
  elif s[0]=="f":
    if search(r,int(s.split()[1])) != None:
      print("yes")
    else:
      print("no")
  elif s[0]=="d":
    
    
    delete(int(s.split()[1]))
  else:
    
    ret = []
    inorder(r)
    print(""," ".join(map(str,ret)))
    ret = []
    preorder(r)
    print(""," ".join(map(str,ret)))

Solution (Python):
class node():
    def __init__(self, key, parent, left, right):
        self.key = key
        self.parent = parent
        self.left = left
        self.right = right

root = None

def insert(z):
    global root

    y = None
    x = root

    while x != None:
        y = x

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

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

def find(key):
    
    x = root
    answer = None

    while x != None:

        if key == x.key:
            answer = x
            break

        if key < x.key:
            x = x.left
        else:
            x = x.right
    
    return answer
    
def delete(key):
    z = find(key)

    if z.left == None and z.right == None:
        if key < z.parent.key:
            z.parent.left = None
        else:
            z.parent.right = None
    
    elif z.left != None and z.right == None :
        if z.key < z.parent.key:
            z.parent.left = z.left
        else:
            z.parent.right = z.left
        
        z.left.parent = z.parent
    
    elif z.left == None and z.right != None :
        if z.key < z.parent.key:
            z.parent.left = z.right
        else:
            z.parent.right = z.right
        
        z.right.parent = z.parent

    elif z.left != None and z.right != None:
        next_node = z.right

        while next_node.left != None:
            next_node = next_node.left

        new_key = next_node.key
        delete(new_key)

        z.key = new_key

def Inorder_TreeWalk(node):
    if node is None:
        return

    Inorder_TreeWalk(node.left)
    print(" " + str(node.key), end="")
    Inorder_TreeWalk(node.right)

def Preorder_TreeWalk(node):
    if node is None:
            return
            
    print(" " + str(node.key), end="")
    Preorder_TreeWalk(node.left)
    Preorder_TreeWalk(node.right)

def Main():
    global root
    n = int(input())
    
    for i in range(n):
        inp = input().split()
        ope = inp[0]

        if ope == "insert":
            insert(node(int(inp[1]), None, None, None))
        
        elif ope == "find":
            target = find(int(inp[1]))

            if target != None:
                print("yes")
            else:
                print("no")

        elif ope == "delete":
            delete(int(inp[1]))

        elif ope == "print":
            Inorder_TreeWalk(root)
            print()
            Preorder_TreeWalk(root)
            print()
Main()

Solution (Python):
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None


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

    def insert(self, val):
        if not self.root:
            self.root = TreeNode(val)
        else:
            parent = None
            cur = self.root
            while cur:
                parent = cur
                if val < cur.val:
                    cur = cur.left
                elif cur.val < val:
                    cur = cur.right

            if val < parent.val:
                parent.left = TreeNode(val)
            elif parent.val < val:
                parent.right = TreeNode(val)

    def find(self, val):
        if not self.root:
            return False
        else:
            cur = self.root
            while cur:
                if val < cur.val:
                    cur = cur.left
                elif cur.val < val:
                    cur = cur.right
                else:
                    return True
            return False

    def remove(self, val):
        self._remove(self.root, val, None)

    def _remove(self, node, val, parent):
        if not node:
            return
        elif val < node.val:
            self._remove(node.left, val, node)
        elif node.val < val:
            self._remove(node.right, val, node)
        else:
            if node.left and node.right:
                
                cur = node.right
                while cur.left:
                    cur = cur.left
                node.val = cur.val
                self._remove(node.right, cur.val, node)
            elif node.left:
                if parent.left == node:
                    parent.left = node.left
                elif parent.right == node:
                    parent.right = node.left
            elif node.right:
                if parent.left == node:
                    parent.left = node.right
                elif parent.right == node:
                    parent.right = node.right
            else:
                if parent.left == node:
                    parent.left = None
                elif parent.right == node:
                    parent.right = None


def inorder(node):
    if node:
        res = []
        res += inorder(node.left)
        res.append(node.val)
        res += inorder(node.right)
        return res
    else:
        return []


def preorder(node):
    if node:
        res = [node.val]
        res += preorder(node.left)
        res += preorder(node.right)
        return res
    else:
        return []


if __name__ == '__main__':
    n = int(input())
    bst = BinarySearchTree()
    for _ in range(n):
        cmd, *num = input().split()
        if cmd == 'insert':
            bst.insert(int(num[0]))
        elif cmd == 'find':
            if bst.find(int(num[0])):
                print('yes')
            else:
                print('no')
        elif cmd == 'delete':
            bst.remove(int(num[0]))
        else:
            for x in inorder(bst.root):
                print(f' {x}', end='')
            print()
            for x in preorder(bst.root):
                print(f' {x}', end='')
            print()

Solution (Python):
class TreeNode:
  def __init__(self, val):
    self.val = val
    self.left = None
    self.right = None

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

  def insert(self, val):
    node = TreeNode(val)
    if self.root is None: 
      self.root = node
      return

    cur_parent = None
    cur_root = self.root

    while cur_root is not None:
      cur_parent = cur_root
      if val > cur_root.val:
        cur_root = cur_root.right
      else:
        cur_root = cur_root.left

    if val > cur_parent.val:
      cur_parent.right = node
    else:
      cur_parent.left = node

  def find(self, val):
    cur_node = self.root

    while cur_node is not None:
      if cur_node.val == val:
        return cur_node
      elif cur_node.val > val:
        cur_node = cur_node.left
      else:
        cur_node = cur_node.right

    return False

  def minValueNode(self, node): 
    current = node 
  
    
    while(current.left is not None): 
        current = current.left  
  
    return current

  def delete(self, root, val):
    if root is None: 
      return root
    elif val < root.val:
      root.left = self.delete(root.left, val)
    elif val > root.val:
      root.right = self.delete(root.right, val)
    else:
      
      if root.left is None: 
        temp = root.right  
        root = None 
        return temp  

      elif root.right is None: 
          temp = root.left  
          root = None
          return temp 

      
      
      temp = self.minValueNode(root.right) 

      
      root.val = temp.val 

      
      root.right = self.delete(root.right, temp.val) 

    return root  

  def print(self):
    self.inorder = []
    self.preorder = []
    self.inorder_dfs(self.root)
    self.preorder_dfs(self.root)

    print(" " + " ".join([ str(i) for i in self.inorder ]))
    print(" " + " ".join([ str(i) for i in self.preorder ]))

  def inorder_dfs(self, root):
    if not root: return

    self.inorder_dfs(root.left)
    self.inorder.append(root.val)
    self.inorder_dfs(root.right)

  def preorder_dfs(self, root):
    if not root: return

    self.preorder.append(root.val)
    self.preorder_dfs(root.left)
    self.preorder_dfs(root.right)


n = int(input())
bst = Bst()
for _ in range(n):
  ins = list(map(str, input().split()))
  order = ins[0]
  if order == "insert":
    val = int(ins[1])
    bst.insert(val)
  elif order == "find":
    val = int(ins[1])
    if not bst.find(val):
      print("no")
    else:
      print("yes")
  elif order == "delete":
    val = int(ins[1])
    bst.delete(bst.root, val)
  elif order == "print":
    bst.print()

Solution (Python):



class Node:
    def __init__(self, id):
        self.id = id
        self.parent = None
        self.left = None
        self.right = None
    
    def __str__(self):
        return 'id={}'.format(self.id)

class BinaryTree:
    def __init__(self):
        self.root = None
        
    def insert(self, node, current_node=None):
        if self.root is None:
            self.root = node
            return
        
        if current_node is None:
            current_node = self.root
            
        if node.id < current_node.id:
            if current_node.left:
                self.insert(node, current_node.left)
            else:
                current_node.left = node
                node.parent = current_node
        else:
            if current_node.right:
                self.insert(node, current_node.right)
            else:
                current_node.right = node
                node.parent = current_node
    
    def delete(self, id, current_node=None):
        if current_node is None:
            current_node = self.root
        
        if id == current_node.id:
            if current_node.left is None and current_node.right is None:
                
                if current_node.parent.left and current_node.parent.left.id == id:
                    current_node.parent.left = None
                else:
                    current_node.parent.right = None
            elif current_node.left and current_node.right:
                result = []
                self.walk_inorder(result, current_node)
                in_id = result[result.index(current_node.id)+1]
                current_node.id = in_id
                self.delete(in_id, current_node.right)
            else:
                child = None
                if current_node.left:
                    child = current_node.left
                else:
                    child = current_node.right
                
                if current_node.parent.left and current_node.parent.left.id == id:
                    child.parent = current_node.parent
                    current_node.parent.left = child
                else:
                    child.parent = current_node.parent
                    current_node.parent.right = child
        elif id < current_node.id:
            if current_node.left:
                self.delete(id, current_node.left)
        elif current_node.id < id:
            if current_node.right:
                self.delete(id, current_node.right)
                
    def walk_inorder(self, result, current_node=None):
        if current_node is None:
            current_node = self.root
        
        if current_node.left:
            self.walk_inorder(result, current_node.left)
            
        result.append(current_node.id)
        
        if current_node.right:
            self.walk_inorder(result, current_node.right)
    
    def walk_preorder(self, result, current_node=None):
        if current_node is None:
            current_node = self.root
        
        result.append(current_node.id)
        
        if current_node.left:
            self.walk_preorder(result, current_node.left)
            
        if current_node.right:
            self.walk_preorder(result, current_node.right)

    def find(self, id, current_node=None):
        if current_node is None:
            current_node = self.root
            
        if current_node.id == id:
            return True
        if id < current_node.id:
            if current_node.left and self.find(id, current_node.left):
                return True
        else:
            if current_node.right and self.find(id, current_node.right):
                return True
        return False

def main():
    n = int(input())
    tree = BinaryTree()
    
    for _ in range(n):
        cmd = input()
        if cmd[0] == 'p':
            result = []
            tree.walk_inorder(result)
            print('', *result)
            
            result = []
            tree.walk_preorder(result)
            print('', *result)
        elif cmd[0] == 'i':
            id = int(cmd.split()[1])
            node = Node(id)
            tree.insert(node)
        elif cmd[0] == 'd':
            id = int(cmd.split()[1])
            tree.delete(id)
        elif cmd[0] == 'f':
            id = int(cmd.split()[1])
            if tree.find(id):
                print('yes')
            else:
                print('no')

if __name__=='__main__':
    main()

Solution (Python):
import sys

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

def insert(key):
    global root
    
    if root.key is None:
        root.key = key
        return
    
    else:
        newNode = Node(key)
        x = root
        while x is not None:
            tmpParent = x 
            if newNode.key < x.key:
                x = x.left
            else:
                x = x.right
        newNode.parent = tmpParent
        if newNode.key < tmpParent.key:
            tmpParent.left = newNode
        else:
            tmpParent.right = newNode

def find(key):
    """
    Find a node with the key (x: a node for search)
    :param key: Key to search
    :return: A node that has the key. Returns None if there is no match,
    """
    global root
    x = root
    while x is not None and x.key != key:
        if key < x.key:
            x = x.left
        else:
            x = x.right
    return x

def delete(key):
    global root
    z = find(key)

    if z.left is None or z.right is None:
        nodeToDelete = z
    else:
        nodeToDelete = getSuccessor(z)

    
    if nodeToDelete.left is not None:
        x = nodeToDelete.left
    else:
        x = nodeToDelete.right

    if x is not None:
        x.parent = nodeToDelete.parent

    if nodeToDelete.parent is None:
        root = x
    elif nodeToDelete == nodeToDelete.parent.left:
        nodeToDelete.parent.left = x
    else:
        nodeToDelete.parent.right = x

    if nodeToDelete != z:
        z.key = nodeToDelete.key

    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    

def getSuccessor(node):
    """
    node の次節点 (中間巡回で次に来る node を返す
    """
    if node.right is not None:
        return getMinimum(node.right)
    y = node.parent
    while y is not None and node == y.right:
        node = y
        y = y.parent
    return y

def getMinimum(node):
    while node.left is not None:
        node = node.left
    return node

def inorder(node, result):
    if node is None:
        return
    inorder(node.left, result)
    result.append(node.key)
    inorder(node.right, result)

def preorder(node, result):
    if node is None:
        return
    result.append(node.key)
    preorder(node.left, result)
    preorder(node.right, result)

def printOrderedResult(node, orderFunction):
    """
    :param node: node (root)
    :param orderFunction: inorder or preorder (function)
    :return: nothing
    """
    result = []
    orderFunction(node, result)
    result = [i for i in map(str, result)]
    print(' ', end='')
    print(' '.join(result))




root = Node()
n = int(input())

for i in range(n):
    command = input()
    try:
        command, key = command.split()
        key = int(key)
        if command == 'insert':
            insert(key)
        elif command == 'find':
            if find(key) is None:
                print('no')
            else:
                print('yes')
        elif command == 'delete':
            delete(key)
    except ValueError: 
        printOrderedResult(root, inorder)
        printOrderedResult(root, preorder)

Solution (Python):
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: 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
        remove_node(p, c, c.right)
    else:
        g = c.right
        while g.left.left: 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))

Solution (Python):
n = int(input())
COM = [list(input().split()) for _ in range(n)]

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

    def inorder(self,List):
        if self.data != None:
            if self.left != None:
                self.left.inorder(List)
            List.append(self.data)
            if self.right != None:
                self.right.inorder(List)
        return List

    def preorder(self,List):
        if self.data != None:
            List.append(self.data)
            if self.left != None:
                self.left.preorder(List)
            if self.right != None:
                self.right.preorder(List)
        return List

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

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

    def find(self,data,sw):
        pt = self.root
        flag = 0
        while pt != None:
            if pt.data == data:
                flag = 1
                if sw == 1:
                    print("yes")
                return 1
            elif pt.data > data:
                pt = pt.left
            else:
                pt = pt.right
        if flag == 0:
            if sw == 1:
                print("no")
            return 0

    def delete(self,data):
        if self.find(data,0) == 1:
            pt = self.root
            while pt != None:
                if pt.data == data:
                    break
                elif pt.data > data:
                    pt = pt.left
                else:
                    pt = pt.right
            if pt.left == None and pt.right == None: 
                if pt.data < pt.parent.data:
                    pt.parent.left , pt = None , None
                else:
                    pt.parent.right , pt = None , None
            elif pt.left != None and pt.right == None: 
                if pt.data < pt.parent.data:
                    pt.parent.left , pt.left.parent , pt = pt.left , pt.parent , None
                else:
                    pt.parent.right , pt.left.parent , pt = pt.left , pt.parent , None
            elif pt.left == None and pt.right != None: 
                if pt.data < pt.parent.data:
                    pt.parent.left , pt.right.parent , pt = pt.right , pt.parent , None
                else:
                    pt.parent.right , pt.right.parent , pt = pt.right , pt.parent , None
            else: 
                y = self.getSuccessor(pt) 
                pt.data = y.data
                if y.right == None:
                    if y.data < y.parent.data:
                        y.parent.left , y = None , None
                    else:
                        y.parent.right , y = None , None
                else:
                    if y.data < y.parent.data:
                        y.parent.left , y.right.parent , y = y.right , y.parent , None
                    else:
                        y.parent.right , y.right.parent , y = y.right , y.parent , None
    def getSuccessor(self,x): 
        if x.right != None:
            return self.getMinimum(x.right)
        y = x.parent
        while y != None and x == y.right:
            x = y
            y = y.parent
        return y

    def getMinimum(self,x):
        while x.left != None:
            x = x.left
        return x

    def print(self):
        print(""," ".join(map(str,self.root.inorder([])))) 
        print(""," ".join(map(str,self.root.preorder([]))))

btree = BTree()
cnt = 0
for i in range(n):
    if COM[i][0] == "insert":
        node = Node(int(COM[i][1]))
        btree.insert(node)
        cnt += 1
    elif COM[i][0] == "find":
        btree.find(int(COM[i][1]),1)
    elif COM[i][0] == "delete":
        btree.delete(int(COM[i][1]))
    else:
        btree.print()