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
import time

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

def insert(z):
    global root
    y = None
    x = root
    while x is not None:
        y = x
        if z.key < x.key:
            x = x.left
        else:
            x = x.right
    z.parent = y
    if y is None:
        root = z
    elif z.key < y.key:
        y.left = z
    else:
        y.right = z

def find(node, key):
    if node is None:
        return False
    elif node.key == key:
        return True
    elif node.key > key:
        return find(node.left, key)
    else:
        return find(node.right, key)

def delete(node, key):
    if node is not None:
        if node.key == key:
            reconstTree(node)
        elif node.key > key:
            delete(node.left, key)
        else:
            delete(node.right, key)

def reconstTree(node):
    if node.left is None and node.right is None:
        if node.parent.left == node:
            node.parent.left = None
        else:
            node.parent.right = None
    elif node.left is not None and node.right is not None:
        sib = node.right
        while sib.left is not None:
            sib = sib.left
        node.key = sib.key
        sib.parent.left = None
    elif node.left is not None:
        if node.parent.left == node:
            node.parent.left = node.left
        else:
            node.parent.right = node.left
        node.left.parent = node.parent
    else:
        if node.parent.left == node:
            node.parent.left = node.right
        else:
            node.parent.right = node.right
        node.right.parent = node.parent

def inorderTreeWalk(node):
    global In
    if node:
        inorderTreeWalk(node.left)
        In.append(str(node.key))
        inorderTreeWalk(node.right)

def preorderTreeWalk(node):
    global Pre
    if node:
        Pre.append(str(node.key))
        preorderTreeWalk(node.left)
        preorderTreeWalk(node.right)

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    del lines[0]

    root = None
    for line in lines:
        if line[0] == "p":
            In = []
            Pre = []
            inorderTreeWalk(root)
            print " " + " ".join(map(str, In))
            preorderTreeWalk(root)
            print " " + " ".join(map(str, Pre))
        else:
            com = line.split()
            if com[0][0] == "i":
                insert(Node(int(com[1])))
            elif com[0][0] == "f":
                if find(root, int(com[1])):
                    print "yes"
                else:
                    print "no"
            else:
                delete(root, int(com[1]))

Submission status: Wrong Answer

Solution code:
class BinarySearchTree:

    def __init__(self):
        self.root = None

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

    def get_inorder_list(self):
        def _get_inorder_list(root):
            l = root.left
            r = root.right
            if l: yield from _get_inorder_list(l)
            yield root.key
            if r: yield from _get_inorder_list(r)
        yield from _get_inorder_list(self.root)

    def get_preorder_list(self):
        def _get_preorder_list(root):
            l = root.left
            r = root.right
            yield root.key
            if l: yield from _get_preorder_list(l)
            if r: yield from _get_preorder_list(r)
        yield from _get_preorder_list(self.root)

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

    def delete(self, k):
        def ldelete(z):
            if z.left and z.right:
                z_key_n = z.left.key
                ldelete(z.left)
                z.key = z_key_n
            else:
                c = z.left if z.left else z.right
                if   z.p == None    : self.root = c
                elif z.key < z.p.key: z.p.left  = c
                else                : z.p.right = c
                if c: c.p = z.p
        z = self.find(k)
        if z: ldelete(z)
# end class BinarySearchTree:

class Node:
    def __init__(self, k):
        self.key = k
        self.p = None
        self.left = None
        self.right = None
#end class Node:
       

if __name__=='__main__':
    m = int(input())

    T = BinarySearchTree()
    for _ in range(m):        
        op = input().split()
        if   op[0] == 'insert': T.insert( Node(int(op[1])) )
        elif op[0] == 'delete': T.delete( int(op[1]) )
        elif op[0] == 'find'  : print("yes" if T.find(int(op[1])) else "no")
        else:
            print("",*T.get_inorder_list())
            print("",*T.get_preorder_list())

Submission status: Wrong Answer

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 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:
       node.label = node.left.label
       node.left = self.delete_node(node.left, node.left.label)
     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: Wrong Answer

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.left)
       node.label = minnode
       node.left = self.delete_node(node.left, 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: Wrong Answer

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 z
        elif left is None and right is not None:
            x = T[p].index(n)
            T[p][x] = right
            T[right][2] = z[2]
            del z
        elif left is not None and right is None:
            x = T[p].index(n)
            T[p][x] = left
            T[left][2] = z[2]
            del z
        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: Wrong Answer

Solution code:
import sys

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

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

    def insert(self, x):
        if self.root is None:
            self.root = Node(x)
            return self

        node = self.root
        while True:
            if x > node.key:
                if node.right is None:
                    node.right = Node(x, node)
                    break
                else:
                    node = node.right
            elif x < node.key:
                if node.left is None:
                    node.left = Node(x, node)
                    break
                else:
                    node = node.left
            else:
                break

        return self

    def remove(self, x):
        node = self.root

        while node is not None:
            if x == node.key:
                parent = node.parent
                if node.left is not None and node.right is None:
                    if x < parent.key:
                        parent.left = node.left
                        node.left.parent = parent
                    else:
                        parent.right = node.left
                        node.left.parent = parent
                elif node.left is None and node.right is not None:
                    if x < parent.key:
                        parent.left = node.right
                        node.right.parent = parent
                    else:
                        parent.right = node.right
                        node.right.parent = parent
                elif node.left is not None and node.right is not None:
                    replace_to = node.left
                    while replace_to.right is not None:
                        replace_to = replace_to.right
                    if replace_to.left is not None:
                        replace_to.parent.right = replace_to.left
                        replace_to.left.parent - replace_to.parent
                    else:
                        replace_to.parent.right = None
                    node.key = replace_to.key
                else:
                    if x < parent.key:
                        parent.left = None
                    else:
                        parent.right = None
                return True
            elif x < node.key:
                node = node.left
            else:
                node = node.right

        return False

    def find(self, x):
        node = self.root
        while node is not None:
            if x == node.key:
                return True
            elif x < node.key:
                node = node.left
            else:
                node = node.right
        return False

    def pre_order(self):
        keys = []
        self.do_pre_order(self.root, keys)
        print(' ' + ' '.join(map(str, keys)))

    def do_pre_order(self, node, keys):
        if node is None:
            return
        keys.append(node.key)
        self.do_pre_order(node.left, keys)
        self.do_pre_order(node.right, keys)

    def in_order(self):
        keys = []
        self.do_in_order(self.root, keys)
        print(' ' + ' '.join(map(str, keys)))

    def do_in_order(self, node, keys):
        if node is None:
            return
        self.do_in_order(node.left, keys)
        keys.append(node.key)
        self.do_in_order(node.right, keys)

# main
tree = BinaryTree()
lines = sys.stdin.readlines()

for line in lines[1:]:
    if len(line.rstrip()) == 0:
        continue

    command = line.rstrip().split(' ')

    if command[0] == 'insert':
        tree.insert(int(command[1]))
    elif command[0] == 'print':
        tree.in_order()
        tree.pre_order()
    elif command[0] == 'find':
        if (tree.find(int(command[1]))):
            print('yes')
        else:
            print('no')
    elif command[0] == 'delete':
        tree.remove(int(command[1]))
    else:
        raise 'unknown command: ' + command[0]

Submission status: Wrong Answer

Solution code:
import sys

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

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

    def insert(self, x):
        if self.root is None:
            self.root = Node(x)
            return self

        node = self.root
        while True:
            if x > node.key:
                if node.right is None:
                    node.right = Node(x, node)
                    break
                else:
                    node = node.right
            elif x < node.key:
                if node.left is None:
                    node.left = Node(x, node)
                    break
                else:
                    node = node.left
            else:
                break

        return self

    def remove(self, x):
        node = self.root

        while node is not None:
            if x == node.key:
                parent = node.parent
                if node.left is not None and node.right is None:
                    if x < parent.key:
                        parent.left = node.left
                        node.left.parent = parent
                    else:
                        parent.right = node.left
                        node.left.parent = parent
                elif node.left is None and node.right is not None:
                    if x < parent.key:
                        parent.left = node.right
                        node.right.parent = parent
                    else:
                        parent.right = node.right
                        node.right.parent = parent
                elif node.left is not None and node.right is not None:
                    replace_to = node.left
                    while replace_to.right is not None:
                        replace_to = replace_to.right
                    if replace_to.left is not None:
                        replace_to.parent.right = replace_to.left
                        replace_to.left.parent = replace_to.parent
                    else:
                        replace_to.parent.right = None
                    node.key = replace_to.key
                else:
                    if x < parent.key:
                        parent.left = None
                    else:
                        parent.right = None
                return True
            elif x < node.key:
                node = node.left
            else:
                node = node.right

        return False

    def find(self, x):
        node = self.root
        while node is not None:
            if x == node.key:
                return True
            elif x < node.key:
                node = node.left
            else:
                node = node.right
        return False

    def pre_order(self):
        keys = []
        self.do_pre_order(self.root, keys)
        print(' ' + ' '.join(map(str, keys)))

    def do_pre_order(self, node, keys):
        if node is None:
            return
        keys.append(node.key)
        self.do_pre_order(node.left, keys)
        self.do_pre_order(node.right, keys)

    def in_order(self):
        keys = []
        self.do_in_order(self.root, keys)
        print(' ' + ' '.join(map(str, keys)))

    def do_in_order(self, node, keys):
        if node is None:
            return
        self.do_in_order(node.left, keys)
        keys.append(node.key)
        self.do_in_order(node.right, keys)

# main
tree = BinaryTree()
lines = sys.stdin.readlines()

for line in lines[1:]:
    if len(line.rstrip()) == 0:
        continue

    command = line.rstrip().split(' ')

    if command[0] == 'insert':
        tree.insert(int(command[1]))
    elif command[0] == 'print':
        tree.in_order()
        tree.pre_order()
    elif command[0] == 'find':
        if (tree.find(int(command[1]))):
            print('yes')
        else:
            print('no')
    elif command[0] == 'delete':
        tree.remove(int(command[1]))
    else:
        raise 'unknown command: ' + command[0]

Submission status: Wrong Answer

Solution code:
import sys

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

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

    def insert(self, x):
        if self.root is None:
            self.root = Node(x)
            return self

        node = self.root
        while True:
            if x > node.key:
                if node.right is None:
                    node.right = Node(x, node)
                    break
                else:
                    node = node.right
            elif x < node.key:
                if node.left is None:
                    node.left = Node(x, node)
                    break
                else:
                    node = node.left
            else:
                break

        return self

    def remove(self, x):
        node = self.root

        while node is not None:
            if x == node.key:
                parent = node.parent
                if node.left is not None and node.right is None:
                    if x < parent.key:
                        parent.left = node.left
                        node.left.parent = parent
                    else:
                        parent.right = node.left
                        node.left.parent = parent
                elif node.left is None and node.right is not None:
                    if x < parent.key:
                        parent.left = node.right
                        node.right.parent = parent
                    else:
                        parent.right = node.right
                        node.right.parent = parent
                elif node.left is not None and node.right is not None:
                    replace_to = node.right
                    while replace_to.left is not None:
                        replace_to = replace_to.left
                    if replace_to.right is not None:
                        replace_to.parent.left = replace_to.right
                        replace_to.right.parent = replace_to.left
                    else:
                        replace_to.parent.left = None
                    node.key = replace_to.key
                else:
                    if x < parent.key:
                        parent.left = None
                    else:
                        parent.right = None
                return True
            elif x < node.key:
                node = node.left
            else:
                node = node.right

        return False

    def find(self, x):
        node = self.root
        while node is not None:
            if x == node.key:
                return True
            elif x < node.key:
                node = node.left
            else:
                node = node.right
        return False

    def pre_order(self):
        keys = []
        self.do_pre_order(self.root, keys)
        print(' ' + ' '.join(map(str, keys)))

    def do_pre_order(self, node, keys):
        if node is None:
            return
        keys.append(node.key)
        self.do_pre_order(node.left, keys)
        self.do_pre_order(node.right, keys)

    def in_order(self):
        keys = []
        self.do_in_order(self.root, keys)
        print(' ' + ' '.join(map(str, keys)))

    def do_in_order(self, node, keys):
        if node is None:
            return
        self.do_in_order(node.left, keys)
        keys.append(node.key)
        self.do_in_order(node.right, keys)

# main
tree = BinaryTree()
lines = sys.stdin.readlines()

for line in lines[1:]:
    if len(line.rstrip()) == 0:
        continue

    command = line.rstrip().split(' ')

    if command[0] == 'insert':
        tree.insert(int(command[1]))
    elif command[0] == 'print':
        tree.in_order()
        tree.pre_order()
    elif command[0] == 'find':
        if (tree.find(int(command[1]))):
            print('yes')
        else:
            print('no')
    elif command[0] == 'delete':
        tree.remove(int(command[1]))
    else:
        raise 'unknown command: ' + command[0]

Submission status: Wrong Answer

Solution code:
#coding:UTF-8
class Node:
    def __init__(self,point):
        self.n=point
        self.left=None
        self.right=None
        
def Insert(t,z):
    y=None
    x=t
    while x!=None:
        y=x
        if z.n<x.n:
            x=x.left
        else:
            x=x.right
    if y==None:
        return z
    else:
        if z.n<y.n:
            y.left=z
        else:
            y.right=z
        return t

def Find(t,p):
    if t.n == p:
        return True
    elif t.left!=None and t.n>p:
        a=Find(t.left,p)
    elif t.right!=None and t.n<p:
        a=Find(t.right,p)
    else:
        return False
    return a

def Delete(t,p):
    if t.left!=None and t.left.n==p:
        if t.left.left==None and t.left.right==None:
            t.left=None
        elif t.left.left==None and t.left.right!=None:
            t.left=t.left.right
        else:
            t.left=t.left.left
    elif t.right!=None and t.right.n==p:
        if t.right.left==None and t.right.right==None:
            t.right=None
        elif t.right.left==None and t.right.right!=None:
            t.right=t.right.right
        else:
            t.right=t.right.left
    else:
        if t.n>p and t.left!=None:
            Delete(t.left,p)
        elif t.n<p and t.right!=None:
            Delete(t.right,p)
            

def Pre(t,l):
    l.append(str(t.n))
    if t.left!=None:
        Pre(t.left,l)
    if t.right!=None:
        Pre(t.right,l)

def In(t,l):
    if t.left!=None:
        In(t.left,l)
    l.append(str(t.n))
    if t.right!=None:
        In(t.right,l)

def BST3(A,n):
    tree=None
    for i in range(n):
        if A[i]=="print":
            PreAns=[]
            InAns=[]
            Pre(tree,PreAns)
            In(tree,InAns)
            print(" "+" ".join(InAns))
            print(" "+" ".join(PreAns))
        else:
            if A[i].split(" ")[0]=="find":
                point=int(A[i].split(" ")[1])
                if Find(tree,point)==True:
                    print("yes")
                else:
                    print("no")
            elif A[i].split(" ")[0]=="delete":
                point=int(A[i].split(" ")[1])
                Delete(tree,point)
            else:    
                z=Node(int(A[i].split(" ")[1]))
                tree=Insert(tree,z)
            
if __name__=="__main__":
    n=int(input())
    A=[]
    for i in range(n):
        A.append(input())
    BST3(A,n)