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: Accepted

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


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

    def insert(self, v):
        x = TreeNode(v)
        if not self.root:
            self.root = x
            return

        r = self.root
        while r is not None:
            parent = r
            if x.val < r.val:
                r = r.left
            else:
                r = r.right

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

    def in_order(self):
        def helper(node):
            return helper(node.left) + [node.val] + helper(node.right) if node else []
        return helper(self.root)

    def pre_order(self):
        def helper(node):
            return [node.val] + helper(node.left) + helper(node.right) if node else []
        return helper(self.root)

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

    def delete(self, key):
        def helper(r, p):
            if not r.left and not r.right:
                if r == p.left:
                    p.left = None
                else:
                    p.right = None
                return

            if r.left and not r.right:
                if r == p.left:
                    p.left = r.left
                else:
                    p.right = r.left
                return
            elif not r.left and r.right:
                if r == p.left:
                    p.left = r.right
                else:
                    p.right = r.right
                return

        if not self.find(key):
            return

        p = None
        r = self.root
        while True:
            if key < r.val:
                p = r
                r = r.left
            elif key > r.val:
                p = r
                r = r.right
            else:
                break

        if not p:
            if not r.left and not r.right:
                self.root = None
                return

        if not r.left or not r.right:
            helper(r, p)
            return

        p = r
        curr = r.right
        while curr.left:
            p = curr
            curr = curr.left

        r.val = curr.val
        helper(curr, p)
        return


test = BST()
n = int(input())
for _ in range(n):
    order = input()
    if order.startswith("insert"):
        i, x = order.split()
        test.insert(int(x))
    elif order.startswith("find"):
        i, x = order.split()
        print("yes" if test.find(int(x)) else "no")
    elif order.startswith("delete"):
        i, x = order.split()
        test.delete(int(x))
    else:
        print(" ",end="")
        print(*test.in_order())
        print(" ",end="")
        print(*test.pre_order())

Submission status: Accepted

Solution code:
NIL = -1


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

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


class BinaryTree():
    def __init__(self, node):
        self.root = node

    def insert(self, key):
        if self.root.key == NIL:
            self.root.key = key
            return

        now = self.root
        while now != NIL:
            parent = now
            if   key < now.key:
                now = now.left
            elif key > now.key:
                now = now.right
            else:
                raise
        
        insert = Node(key, parent)

        if   insert.key < parent.key:
            parent.left = insert
        elif insert.key > parent.key:
            parent.right = insert
        else:
            raise

    def find(self, key):
        now = self.root
        while now != NIL:
            if   key < now.key:
                now = now.left
            elif key > now.key:
                now = now.right
            else:
                break

        return now

    def delete(self, key):
        z = self.find(key)
        if isinstance(z, int):
            return

        if z.left == NIL or z.right == NIL:
            y = z
        else:
            y = self.get_successor(z)

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

        if x != NIL:
            x.parent = y.parent

        if y.parent == NIL:
            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 get_successor(self, x):
        if x.right != NIL:
            return self.get_minimum(x.right)

        y = x.parent
        while y != NIL and x == y.right:
            x = y
            y = y.parent
        return y

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

        return x

    def treewalk_inorder(self, node):
        if isinstance(node, int):
            return

        self.treewalk_inorder(node.left)
        print(f" {node.key}", end="")
        self.treewalk_inorder(node.right)

    def treewalk_preorder(self, node):
        if isinstance(node, int):
            return

        print(f" {node.key}", end="")
        self.treewalk_preorder(node.left)
        self.treewalk_preorder(node.right)



m = int(input())

root = Node()
binary_tree = BinaryTree(root)


for _ in range(m):

    command, *list_num = input().split()

    if   command == "insert":
        k = int(list_num[0])
        binary_tree.insert(k)
    elif command == "find":
        k = int(list_num[0])
        if isinstance(binary_tree.find(k), int):
            print("no")
        else:
            print("yes")
    elif command == "delete":
        k = int(list_num[0])
        binary_tree.delete(k)
    elif command == "print":
        binary_tree.treewalk_inorder(root)
        print()
        binary_tree.treewalk_preorder(root)
        print()
    else:
        raise

Submission status: Accepted

Solution code:
class BSTree:
    def __init__(self):
        self.value, self.left, self.right = (None,) * 3

    def add(self, x):
        if self.value is None:
            self.value = x
        elif x < self.value:
            if self.left is None:
                self.left = BSTree()
            self.left.add(x)
        else:
            if self.right is None:
                self.right = BSTree()
            self.right.add(x)

    def find(self, x):
        if self.value == x:
            return True
        if self.left is not None and x < self.value:
            return self.left.find(x)
        if self.right is not None and self.value < x:
            return self.right.find(x)
        return False

    def delete_min(self):
        if self.left is None:
            return self.value, None
        else:
            value, self.left = self.left.delete_min()
            return value, self

    def delete(self, x):
        if self.value == x:
            if self.left is not None and self.right is not None:
                self.value, self.right = self.right.delete_min()
            else:
                return self.left or self.right
        elif x < self.value and self.left is not None:
            self.left = self.left.delete(x)
        elif self.value < x and self.right is not None:
            self.right = self.right.delete(x)
        return self

    def preorder(self):
        def get(t):
            return [] if t is None else t.preorder()
        return [self.value] + get(self.left) + get(self.right)

    def inorder(self):
        def get(t):
            return [] if t is None else t.inorder()
        return get(self.left) + [self.value] + get(self.right)


def print_list(l):
    print(' ' + ' '.join(map(str, l)))


def main():
    n = input()
    t = BSTree()
    for _ in range(int(n)):
        ip = input().split()
        if len(ip) == 1:
            print_list(t.inorder())
            print_list(t.preorder())
        else:
            command, k = ip[0], int(ip[1])
            if command == 'insert':
                t.add(k)
            elif command == 'find':
                print('yes' if t.find(k) else 'no')
            else:
                t = t.delete(k)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class BST:
  def __init__(self):
    self.root = None
  
  def insert(self, data):
    z = Node(data)
    y = None
    x = self.root

    while x:
      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):
    x = self.root
    z = Node(data)
    while x and data != x.data:
      if z.data < x.data:
        x = x.left
      else:
        x = x.right
    return x
    """if x is not None:
      return True
    else:
      return False"""

  def getMinimum(self, z):
    while z.left:
      z = z.left
    return z

  def getSuccessor(self, z):
    if z.right:
      return self.getMinimum(z.right)
    
    y = z.parent
    while y and z == y.right:
      z = y
      y = y.parent
    return y
      
  def delete(self, data):
    z = self.find(data)
    if z is None:
      return 

    #z = Node(data)
    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.data = y.data

  def print(self):
    print('',' '.join(map(str, self.root.inorder())))
    print('',' '.join(map(str, self.root.preorder())))


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

  def inorder(self):
    in_list = []
    if self.left:
      in_list += self.left.inorder()
    in_list += [self.data]
    if self.right:
      in_list += self.right.inorder()
    return in_list
  
  def preorder(self):
    pre_list = []
    pre_list += [self.data]
    if self.left:
      pre_list += self.left.preorder()
    if self.right:
      pre_list += self.right.preorder()
    return pre_list

tree = BST()
n = int(input())
for _ in range(n):
  inp = input().split()
  if len(inp) == 2:
    if inp[0] == "insert":
      tree.insert(int(inp[1]))
    elif inp[0] == "find":
      x = tree.find(int(inp[1]))
      if x is not None:
        print("yes")
      else:
        print("no")
    else:
      tree.delete(int(inp[1]))
  else:
    tree.print()

Submission status: Accepted

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

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

    return root

def printPreorderList(p):
    if p == None:
        return
    print("",p.key,end = "")
    printPreorderList(p.left)
    printPreorderList(p.right)

def printInorderList(p):
    if p == None:
        return
    printInorderList(p.left)
    print("",p.key,end = "")
    printInorderList(p.right)

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

def delete(key, root):
    z = find(key, root)
    if z == None:
        return root
    elif z.left == None and z.right == None: 
        if z.p.left == z:
            z.p.left = None
        else:
            z.p.right = None
        #z = None
    elif z.left != None and z.right == None:
        if z == root:
            root = z.left

        if z.p.left == z:
            z.p.left = z.left
        else:
            z.p.right = z.left
        z.left.p = z.p
        #z = None
    elif z.left == None and z.right != None:
        if z == root:
            root = z.right

        if z.p.left == z:
            z.p.left = z.right
        else:
            z.p.right = z.right
        z.right.p = z.p
        #z = None
    else:
        y = z.right
        while y.left != None:
            y = y.left
        z.key = y.key
        if y.right != None:
            y.right.p = y.p
        if y.p.left == y:
            y.p.left = None
        else:
            y.p.right = None
        #y = None

    return root

n = int(input())
root = None
for ni in range(n):
    s = input()
    if s[0] == "i":
        s, key = s.split()
        key = int(key)
        root = insert(Node(key), root)
    elif s[0] == "p":
        printInorderList(root)
        print()
        printPreorderList(root)
        print()
    elif s[0] == "f":
        s, key = s.split()
        key = int(key)
        ans = find(key, root)
        if ans == None:
            print("no")
        else:
            print("yes")
    elif s[0] == "d":
        s, key = s.split()
        key = int(key)
        root = delete(key, root)

Submission status: Accepted

Solution code:
class Node():
    def __init__(self, key):
        self.key = key
        self.left = self.right = None
        
def insert(key):
    global root

    x = root
    y = None
    while x:x, y = x.left if key < x.key else x.right , x
    if y == None:root = Node(key)
    elif y.key < key:y.right = Node(key)
    else:y.left = Node(key)
        
        
def pre(node):
    if node == None:return
    print('',node.key, end = '');pre(node.left);pre(node.right)
    
def ino(node):
    if node == None:return
    ino(node.left);print('',node.key,end='');ino(node.right)

def find(node, key):
    if node == None:
        print('no');return
    if node.key == key:
        print('yes');return
    elif node.key > key:
        find(node.left, key)
    else:
        find(node.right, key)

def delete(node, key):
    x = node
    while x and x.key != key :
        x, y = x.left if key < x.key else x.right, x
    if x == None:
        return
    else:
        if key < y.key:f = 1
        else:f = 0
        if x.left == None and x.right == None:
            if f:y.left = None
            else:y.right = None
        elif x.right == None:
            if f:y.left = x.left
            else:y.right = x.left
        elif x.left == None:
            if f:y.left = x.right
            else:y.right = x.right
        else:
            a = x.right
            c = 0
            b = 1
            while a:a, b, c = a.left if a.left != None and a.right != None else a.left if a.left != None else None  , a, b
            if c == 1:
                b.left = x.left
                if f:y.left = b
                else:y.right = b
            else:
                c.left = b.right
                x.key = b.key
                
                
            
        
        
    

n = int(input())
root = None
for j in range(n):
    s, *i = input().split()
    if s[0] == 'i':insert(int(i[0]))
    elif s[0] == 'f':
        find(root, int(i[0]))
    elif s[0] == 'd':
        delete(root, int(i[0]))
    else:
        ino(root);print();pre(root);print()

Submission status: Accepted

Solution code:
class Tree():
    def __init__(self):
        self.nodes = {}
        self.root = None

    def add_node(self, key):
        if key not in self.nodes:
            self.nodes[key] = Node(key)

    def insert(self, z_key):
        self.add_node(z_key)
        z = self.nodes[z_key]
        y = None  # xの親
        x = self.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:
            self.root = z
        elif z.key < y.key:
            y.left = z
        else:
            y.right = z

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

    def delete(self, key):
        node = self.find(key)
        if node:
            if bool(node.left) ^ bool(node.right):
                node.delete_1()
            elif bool(node.left) & bool(node.right):
                #  2つもつ場合
                next = node.getSuccesor()
                self.delete(next.key)
                node.key = next.key
            else:
                # 1つも持たない場合
                if node.key < node.parent.key:
                    node.parent.left = None
                else:
                    node.parent.right = None

    def __str__(self):
        ans_in, ans_pre = [], []
        self.root.in_walk(ans_in)
        self.root.pre_walk(ans_pre)
        str_in = ' ' + ' '.join(map(str, ans_in))
        str_pre = ' ' + ' '.join(map(str, ans_pre))
        return str_in + '\n' + str_pre


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

    def pre_walk(self, ans):
        ans.append(self.key)
        if self.left:
            self.left.pre_walk(ans)
        if self.right:
            self.right.pre_walk(ans)

    def in_walk(self, ans):
        if self.left:
            self.left.in_walk(ans)
        ans.append(self.key)
        if self.right:
            self.right.in_walk(ans)

    def getSuccesor(self):
        if self.right is not None:
            return self.right.getMinimum()
        p = self.parent
        while (p is not None) & (self == p.right):
            self = p
            p = p.parent
        return p

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

    def delete_1(self):
        p = self.parent
        for c in (self.left, self.right):
            if c:
                c.parent = p
                if self.key < p.key:
                    p.left = c
                else:
                    p.right = c


# ここからmain
tree = Tree()
n = int(input())
for i in range(n):
    line = list(map(str, input().split()))
    if line[0] == 'insert':
        key = int(line[1])
        tree.insert(key)
    elif line[0] == 'find':
        key = int(line[1])
        x = tree.find(key)
        if x:
            print('yes')
        else:
            print('no')
    elif line[0] == 'delete':
        key = int(line[1])
        tree.delete(key)
    else:
        print(tree)

Submission status: Accepted

Solution code:
class Node:
    def __init__(self, k):
        self.parent = None
        self.childs = [None, None]
        self.key = k


class Tree:
    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.childs[0]
            else:
                x = x.childs[1]
        z.parent = y
        if y == None:
            self.root = z
        elif z.key < y.key:
            y.childs[0] = z
        else:
            y.childs[1] = z

    def find(self, k):
        x = self.root
        while x != None:
            if k == x.key:
                return x
            if k < x.key:
                x = x.childs[0]
            else:
                x = x.childs[1]
        return None

    def delete(self, k):
        z = self.find(k)
        if z == None:
            return
        if z.childs[0] == None and z.childs[1] == None:
            p = z.parent
            if p != None:
                for i, v in enumerate(p.childs):
                    if v == z:
                        p.childs[i] = None
                        break
        elif z.childs[0] != None and z.childs[1] != None:
            y = z.childs[1]
            while y.childs[0] != None:
                y = y.childs[0]
            nk = y.key
            self.delete(nk)
            z.key = nk
        else:
            p = z.parent
            c = z.childs[0] if z.childs[0] != None else z.childs[1]
            c.parent = p
            if p != None:
                for i, v in enumerate(p.childs):
                    if v == z:
                        p.childs[i] = c
                        break


def preorder(p):
    s = ""
    if p == None:
        return ""
    s += f"{p.key} "
    s += preorder(p.childs[0])
    s += preorder(p.childs[1])
    return s


def inorder(p):
    s = ""
    if p == None:
        return ""
    s += inorder(p.childs[0])
    s += f"{p.key} "
    s += inorder(p.childs[1])
    return s


n = int(input())

t = Tree()
for i in range(n):
    v = input().split()
    if v[0] == "insert":
        t.insert(Node(int(v[1])))
    elif v[0] == "find":
        print("yes" if t.find(int(v[1])) != None else "no")
    elif v[0] == "delete":
        t.delete(int(v[1]))
    else:
        print(" "+inorder(t.root).strip())
        print(" "+preorder(t.root).strip())

Submission status: Accepted

Solution code:
import sys

class Node:
    def __init__(self,data=None):
        self.data  = data
        self.left  = None
        self.right = None
    
def search(node,x):
    if node is None:
        return 'no'
    elif node.data == x:
        return 'yes'
    elif node.data > x:
        return search(node.left,x)
    else:
        return search(node.right,x)

def insert(node,x):
    if node is None:
        node = Node(x)
    elif node.data == x:
        return node
    elif node.data > x:
        node.left = insert(node.left,x)
    else:
        node.right = insert(node.right,x)
    return node

def search_min(node):
    if node.left is None:
        return node.data
    return search_min(node.left)

def delete_min(node):
    if node.left is None:
        return node.right
    node.left = delete_min(node.left)
    return node

def delete(node,x):
    if node:
        if x == node.data:
            if node.left is None:
                return node.right
            elif node.right is None:
                return node.left
            else:
                node.data = search_min(node.right)
                node.right = delete_min(node.right)
        elif x < node.data:
            node.left = delete(node.left,x)
        else:
            node.right = delete(node.right,x)
    return node

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

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

    def delete(self,x):
        self.root = delete(self.root,x)

def mid_walk(node):
    if node is None:
        return 
    yield from mid_walk(node.left)    
    yield node.data
    yield from mid_walk(node.right)

def pre_walk(node):
    if node is None:
        return 
    yield node.data
    yield from pre_walk(node.left)
    yield from pre_walk(node.right)

n = int(input())
bt = BST()
for line in sys.stdin:
    if line[:1] == 'i':
        bt.insert(int(line[7:]))
    elif line[:1] == 'f':
        print(bt.search(int(line[5:])))
    elif line[:1] == 'p':
        print(' '+' '.join(map(str,mid_walk(bt.root))))
        print(' '+' '.join(map(str,pre_walk(bt.root))))
    else:
        bt.delete(int(line[7:]))

Submission status: Accepted

Solution code:
class Node:
    def __init__(self, value, parent):
        self.val = value
        self.left = None
        self.right = None
        self.parent = parent

class BinarySearchTree:
    def __init__(self):
        self.root = None
    
    def insert(self,key):
        node = Node(key, None)
        if self.root == None:
            self.root = node
        else:
            curr_node = self.root
            while curr_node:
                parent_node = curr_node
                if key < curr_node.val:
                    curr_node = curr_node.left
                else:
                    curr_node = curr_node.right
            node.parent = parent_node
            if key < parent_node.val:
                parent_node.left = node
            else:
                parent_node.right = node
     
    def find(self, key):
        curr_node = self.root
        while curr_node and curr_node.val != key:
            if curr_node.val < key:
                curr_node = curr_node.right
            else:
                curr_node = curr_node.left
        return curr_node
    
    # def getMax(self, node):
    #     while node.right:
    #         node = node.right
    #     return node
    
    # def getNode(self, key):
    #     curr_node = self.root
    #     while curr_node and curr_node.val != key:
    #         if key < curr_node.val:
    #             curr_node = curr_node.left
    #         else:
    #             curr_node = curr_node.right
    #     return curr_node   

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

    def getSuccessor(self,node):
        if node.right:
            return self.getMinimum(node.right)

        parent_node = node.parent
        while parent_node and node != parent_node.left:
            node = parent_node
            parent_node = node.parent
        return parent_node
    
    def delete(self, key):
        node = self.find(key)
        if node:
            if node.left == None or node.right == None:
                y = node
            else:
                y = self.getSuccessor(node)

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

            if x != None:
                x.parent = y.parent

            if y.parent == None:
                self.root = x
            elif y.parent.left == y:
                y.parent.left = x
            else:
                y.parent.right = x

            if y != node:
                node.val = y.val


    def preorderTraversal(self, node):
        result = []
        if node == None:
            return result
        result += [node.val]
        result += self.preorderTraversal(node.left)
        result += self.preorderTraversal(node.right)
        return result 


        
    def inorderTraversal(self, node):
        result = []
        if node == None:
            return result
        result += self.inorderTraversal(node.left)
        result += [node.val]
        result += self.inorderTraversal(node.right)
        return result

N = int(input())
command = []
for i in range(N):
    command.append(tuple(input().split()))

T = BinarySearchTree()
for com in command:
    if com[0] == 'insert':
        T.insert(int(com[1]))
    if com[0] == 'find':
        flag = T.find(int(com[1]))
        if flag != None:
            print('yes')
        else:
            print('no')
    if com[0] == 'delete':
        T.delete(int(com[1]))
    if com[0] == 'print':
        In = T.inorderTraversal(T.root)
        Pre = T.preorderTraversal(T.root)
        print(' ' + ' '.join(list(map(str, In))))
        print(' ' + ' '.join(list(map(str, Pre))))