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



import sys
sys.setrecursionlimit(2**20)  


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


def pre_parse(T: dict, u: int, pre_ls: list):
    
    if u == None:
        return
    pre_ls.append(u)
    pre_parse(T, T[u].left, pre_ls)  
    pre_parse(T, T[u].right, pre_ls)


def in_parse(T, u, in_ls):
    if u == None:
        return
    
    in_parse(T, T[u].left, in_ls)
    in_ls.append(u)
    in_parse(T, T[u].right, in_ls)


def insert(T, ROOT, z):
    '''
    zは接点番号(そしてその接点番号が内容でもある)
    この接点番号を二分探索木の条件に従うように挿入する。
    '''
    
    if ROOT == z:
        T[z] = Node()
    
    else:
        T[z] = Node()  
        x = ROOT
        while x is not None:  
            next_parent = x  
            if z < x:  
                x = T[x].left
            else:
                x = T[x].right
        T[z].parent = next_parent
        
        if z < next_parent:
            T[next_parent].left = z
        else:
            T[next_parent].right = z


def find(T, ROOT, k):
    '''
    Tからkを見つけ出す。見つからなかったらNoneを返す
    ひたすらkの大きさによって左右のパスをたどっていくだけ
    (いま辞書でノードを管理しているので、`k in T.keys()`で済むことではあるんだけど(オーダーは大きくなる)))
    '''
    x = ROOT  
    while x is not None and x != k:
        if k < x:
            x = T[x].left
        else:
            x = T[x].right
    return x


def delete_node(T, z):
    
    if (T[z].left is None) and (T[z].right is None):
        
        parent = T[z].parent
        if T[parent].left == z:
            T[parent].left = None
        elif T[parent].right == z:
            T[parent].right = None
        else:
            raise ValueError('something wrong in case 1')
        del T[z]
    
    elif T[z].right is None:
        
        
        parent = T[z].parent
        z_is_left = True if T[parent].left == z else False
        child = T[z].left
        if z_is_left:
            T[parent].left = child
        else:
            T[parent].right = child
        T[child].parent = parent
        del T[z]
    elif T[z].left is None:
        parent = T[z].parent
        z_is_left = True if T[parent].left == z else False
        child = T[z].right
        if z_is_left:
            T[parent].left = child
        else:
            T[parent].right = child
        T[child].parent = parent
        del T[z]
    
    elif (T[z].left is not None) and (T[z].right is not None):
        
        parent = T[z].parent
        left, right = T[z].left, T[z].right
        node_next_more = get_min_in_descendants(
            T, T[z].right)  
        next_more_right = T[node_next_more].right
        next_more_parent = T[node_next_more].parent
        
        if parent is None:
            if node_next_more == right:
                
                T[right].parent = None
                T[right].left = left
                ROOT = right
                del T[z]
                return
            else:
                
                
                T[node_next_more].left = left
                T[node_next_more].right = right
                T[node_next_more].parent = None
                T[left].parent = node_next_more  
                T[right].parent = node_next_more  
                
                if next_more_right is not None:
                    T[next_more_right].parent = next_more_parent
                ROOT = node_next_more
                del T[z]
                return
        else:  
            
            z_is_left = True if T[parent].left == z else False
            if node_next_more == right:
                if z_is_left:
                    T[parent].left = right
                else:
                    T[parent].right = right
                T[right].parent = parent
                T[right].left = left
                del T[z]
                return
            else:  
                
                if z_is_left:
                    T[parent].left = node_next_more
                else:
                    T[parent].right = node_next_more
                
                T[node_next_more].left = T[z].left
                T[node_next_more].right = T[z].right
                T[node_next_more].parent = parent
                T[left].parent = node_next_more  
                T[right].parent = node_next_more  
                
                T[next_more_parent].left = next_more_right
                if next_more_right is not None:
                    T[next_more_right].parent = next_more_parent

                del T[z]
                return

        
        
        
        
        

        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        

        


def get_min_in_descendants(T, z):
    x = z
    while T[x].left is not None:
        x = T[x].left
    return x


def print_result(T):
    pre_ls, in_ls = [], []
    in_parse(T, ROOT, in_ls)
    pre_parse(T, ROOT, pre_ls)
    print('', *in_ls)
    print('', *pre_ls)


    
N = int(input())
T = {}
for i in range(N):
    tmp = input()
    if tmp.startswith('print'):  
        print_result(T)
    elif tmp.startswith('insert'):
        z = int(tmp.split()[1])
        if i == 0:
            ROOT = z
        insert(T, ROOT, z)
    elif tmp.startswith('find'):
        z = int(tmp.split()[1])
        if find(T, ROOT, z) is None:
            print('no')
        else:
            print('yes')
    elif tmp.startswith('delete'):
        z = int(tmp.split()[1])
        delete_node(T, z)

Solution (Python):
from typing import List, Optional


class Node:
	def __init__(self, key) -> None:
		self.key: int = key
		self.left: Optional[Node] = None
		self.right: Optional[Node] = None
		self.parent: Optional[Node] = None


class Tree:
	def __init__(self) -> None:
		self.root: Optional[Node] = None


def insert(T: Tree, z: Node) -> None:
	y: Optional[Node] = None
	x: Optional[Node] = T.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:
		T.root = z
	elif z.key < y.key:
		y.left = z
	else:
		y.right = z


def find(k: int) -> Optional[Node]:
	z = T.root
	while z is not None:
		if k == z.key:
			return z
		elif k < z.key:
			z = z.left
		else:
			z = z.right
	return None

def tree_minimum(x: Node) -> Node:
	while x.left is not None:
		x = x.left
	return x


def tree_successor(x: Node) -> Node:
	if x.right is not None:
		return tree_minimum(x.right)
	y: Optional[Node] = x.parent
	while y is not None and x == y.right:
		x = y
		y = y.parent
	return y


def delete(z: Node) -> None:
	x: Optional[Node] = None
	y: Optional[Node] = None
	if (z.left is None or z.right is None):
		y = z
	else:
		y = tree_successor(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:
		T.root = x
	elif y == y.parent.left:
		y.parent.left = x
	else:
		y.parent.right = x
	if y != z:
		z.key = y.key

def inorder(z: Optional[Node]):
	if z is not None:
		inorder(z.left)
		print(f" {z.key}", end="")
		inorder(z.right)


def preorder(z: Optional[Node]):
	if z is not None:
		print(f" {z.key}", end="")
		preorder(z.left)
		preorder(z.right)


if __name__ == "__main__":
	m = int(input())
	T = Tree()
	for _ in range(m):
		command = list(input().split())
		if command[0] == "insert":
			z = Node(int(command[1]))
			insert(T, z)
		elif command[0] == "find":
			key = int(command[1])
			z = find(key)
			if z is not None:
				print("yes")
			else:
				print("no")
		elif command[0] == "delete":
			key = int(command[1])
			z = find(key)
			if z is not None:
				delete(z)
		else:
			inorder(T.root)
			print("")
			preorder(T.root)
			print("")

Solution (Python):




import sys


import sys


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


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

    def insert(self, x):
        new = Node(x)
        x_parent = self.root
        next = self.root

        while next is not None:
            x_parent = next
            if x < x_parent.key:
                next = x_parent.left
            else:
                next = x_parent.right

        if x_parent is None:
            self.root = new
        elif x < x_parent.key:
            new.parent = x_parent
            x_parent.left = new
        else:
            new.parent = x_parent
            x_parent.right = new
        return

    def preorder(self, node):
        print(' {}'.format(node.key), end='')

        if node.left:
            self.preorder(node.left)
        if node.right:
            self.preorder(node.right)
        return

    def inorder(self, node):
        if node.left:
            self.inorder(node.left)

        print(' {}'.format(node.key), end='')

        if node.right:
            self.inorder(node.right)

    def find(self, num, node):
        if num < node.key:
            if node.left:
                self.find(num, node.left)
            else:
                print('no')
        elif num > node.key:
            if node.right:
                self.find(num, node.right)
            else:
                print('no')
        else:
            print('yes')
            return

    def find2del(self, num, node):
        if num < node.key:
            ans = self.find2del(num, node.left)
            return ans
        elif num > node.key:
            ans = self.find2del(num, node.right)
            return ans
        else:
            return node

    def successor(self, node):
        if node.right:
            nex = node.right
            while nex.left:
                nex = nex.left
            return nex

        nex = node.parent
        while nex & (nex.right == node):
            node = nex
            nex = nex.parent
        return nex

    def delete(self, num, node):
        
        node_del = self.find2del(num, node)
        z = node_del
        if (node_del.left is not None) & (node_del.right is not None):
            node_del = self.successor(node_del)

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

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

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

        if z != node_del:
            z.key = node_del.key

m = int(input())
tree = Tree()

for i in range(m):
    command = list(sys.stdin.readline().strip().split())
    if command[0] == 'print':
        tree.inorder(tree.root)
        print()
        tree.preorder(tree.root)
        print()
    else:
        num = command[1]
        command = command[0]
        num = int(num)
        if command == 'insert':
            tree.insert(num)
        elif command == 'find':
            tree.find(num, tree.root)
        else:
            tree.delete(num, tree.root)

Solution (Python):
import sys
input = sys.stdin.readline

class Node:
    __slots__ = ['value', 'parent', 'left', 'right']
    def __init__(self, value: int, parent: 'Node' = None):
        self.value = value
        self.parent = parent
        self.left: Node = None
        self.right: Node = None
    def inParse(self):
        if self.value == None:
            return
        if self.left != None:
            self.left.inParse()
        print(' {}'.format(self.value), end='')
        if self.right != None:
            self.right.inParse()
    def preParse(self):
        if self.value == None:
            return
        print(' {}'.format(self.value), end='')
        if self.left != None:
            self.left.preParse()
        if self.right != None:
            self.right.preParse()

class BinarySearchTree:
    __slots__ = ['root']
    def __init__(self):
        self.root: Node = None
    def insert(self, x: int):
        if self.root == None:
            self.root = Node(x)
            return
        parent, current = None, self.root
        while current:
            parent = current
            if x < current.value:
                current = current.left
            else:
                current = current.right
        if x < parent.value:
            parent.left = Node(x, parent)
        else:
            parent.right = Node(x, parent)
    def find(self, x: int):
        y = self.root
        while y != None and y.value != x:
            if y.value > x:
                y = y.left
            else:
                y = y.right
        return y
    def getMinimum(self, x: Node):
        while x.left != None:
            x = x.left
        return x
    def getSuccer(self, x: Node):
        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 deleteNode(self, z: Node):
        if z.left == None or z.right == None:
            y = z
        else:
            y = self.getSuccer(z)
        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 != z:
            z.value = y.value
        
def main():
    tree = BinarySearchTree()
    n = int(input())
    for _ in range(n):
        inp = input()
        if inp[0] == 'i':
            com, num = inp.split()
            tree.insert(int(num))
        elif inp[0] == 'f':
            com, num = inp.split()
            if tree.find(int(num)):
                print('yes')
            else:
                print('no')
        elif inp[0] == 'd':
            com, num = inp.split()
            y = tree.find(int(num))
            tree.deleteNode(y)
        else:
            tree.root.inParse()
            print()
            tree.root.preParse()
            print()

if __name__=='__main__': main()

Solution (Python):
class Node():
    def __init__(self, key, p, l, r):
        self.key, self.p, self.l, self.r = key, p, l, r


class BinarySearchTree():
    def __init__(self):
        self.tree = []
        self.root = -1

    def insert(self, key):
        y = -1  
        x = self.root
        while x != -1:
            y = x
            if key < self.tree[x].key:
                x = self.tree[x].l
            else:
                x = self.tree[x].r
        self.tree.append(Node(key, y, -1, -1))
        z = len(self.tree) - 1
        if y == -1:
            self.root = z
        elif key < self.tree[y].key:
            self.tree[y].l = z
        else:
            self.tree[y].r = z

    def find(self, key, x=0):
        while x != -1 and key != self.tree[x].key:
            if key < self.tree[x].key:
                x = self.tree[x].l
            else:
                x = self.tree[x].r
        return x

    def delete(self, key):
        node = self.find(key)
        self.delete_node(node)

    def delete_node(self, z):
        if self.tree[z].l == -1 or self.tree[z].r == -1:
            y = z
        else:
            y = self.get_successor(z)
        if self.tree[y].l != -1:
            x = self.tree[y].l
        else:
            x = self.tree[y].r
        if x != -1:
            self.tree[x].p = self.tree[y].p
        if self.tree[y].p == -1:
            self.root = x
        elif y == self.tree[self.tree[y].p].l:
            self.tree[self.tree[y].p].l = x
        else:
            self.tree[self.tree[y].p].r = x
        if y != z:
            self.tree[z].key = self.tree[y].key

    def get_successor(self, x):
        if self.tree[x].r != -1:
            return self.get_minimum(self.tree[x].r)
        y = self.tree[x].p
        while y != -1 and x == self.tree[y].r:
            x = y
            y = self.tree[y].p
        return y

    def get_minimum(self, x):
        while self.tree[x].l != -1:
            x = self.tree[x].l
        return x

    def preorder_traversal(self, u=0):
        if u == -1:
            return
        print(' ' + str(self.tree[u].key), end='')
        self.preorder_traversal(self.tree[u].l)
        self.preorder_traversal(self.tree[u].r)

    def inorder_traversal(self, u):
        if u == -1:
            return
        self.inorder_traversal(self.tree[u].l)
        print(' ' + str(self.tree[u].key), end='')
        self.inorder_traversal(self.tree[u].r)


def main():
    n = int(input())
    bst = BinarySearchTree()
    for _ in range(n):
        order = input().split()
        if order[0] == 'insert':
            key = int(order[1])
            bst.insert(key)
        elif order[0] == 'print':
            bst.inorder_traversal(0)
            print('')
            bst.preorder_traversal(0)
            print('')
        elif order[0] == 'find':
            key = int(order[1])
            print('yes' if bst.find(key) != -1 else 'no')
        elif order[0] == 'delete':
            key = int(order[1])
            bst.delete(key)


if __name__ == '__main__':
    main()

Solution (Python):

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


def insert(T, z):
    y = None
    x = T
    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:
        T = z
    elif z.key < y.key:
        y.left = z
    else:
        y.right = z

    return T


def preorder(T, ret):
    ret.append(T.key)

    if T.left is not None:
        preorder(T.left, ret)

    if T.right is not None:
        preorder(T.right, ret)


def inorder(T, ret):
    if T.left is not None:
        inorder(T.left, ret)

    ret.append(T.key)

    if T.right is not None:
        inorder(T.right, ret)


def find(T, key):
    if key == T.key:
        return T

    elif key < T.key:
        if T.left is not None:
            ret = find(T.left, key)
            if ret is not None:
                return ret
    else:
        if T.right is not None:
            ret = find(T.right, key)
            if ret is not None:
                return ret

    return None


def delete(T, key):
    if T is None:
        return None
    if key < T.key:
        delete(T.left, key)
    elif key > T.key:
        delete(T.right, key)
    else:
        _delete(T, key)


def _delete(T, key):
    parent = T.parent
    if T.left is None and T.right is None:
        if parent.left == T:
            parent.left = None
        else:
            parent.right = None
        T = None
    elif T.left is None or T.right is None:
        if parent.left == T:
            if T.left:
                parent.left = T.left
                T.left.parent = parent
            else:
                parent.left = T.right
                T.right.parent = parent
        else:
            if T.left:
                parent.right = T.left
                T.left.parent = parent
            else:
                parent.right = T.right
                T.right.parent = parent
        T = None
    else:
        nextnode = T.right
        while nextnode.left:
            nextnode = nextnode.left
        T.key = nextnode.key
        delete(nextnode, nextnode.key)


def main():
    m = int(input())
    Tree = None
    for i in range(m):
        cmd, *v = input().split()
        if cmd == "print":
            print(" ", end="")
            inans = []
            inorder(Tree, inans)
            print(*inans)
            print(" ", end="")
            preans = []
            preorder(Tree, preans)
            print(*preans)
        elif cmd == "insert":
            z = int(v[0])
            znode = Node(z)
            Tree = insert(Tree, znode)
        elif cmd == "find":
            z = int(v[0])
            if find(Tree, z) == None:
                print("no")
            else:
                print("yes")
        else:
            z = int(v[0])
            delete(Tree, z)


if __name__ == '__main__':
    main()

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

    def prewalk(self):
        ret = [self.key]
        if self.left:
            ret += self.left.prewalk()
        if self.right:
            ret += self.right.prewalk()
        return ret

    def inwalk(self):
        ret = []
        if self.left:
            ret += self.left.inwalk()
        ret += [self.key]
        if self.right:
            ret += self.right.inwalk()
        return ret


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

    def insert(self, key):
        z = Node(key)
        y = None
        x = self.root
        while x:
            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 and x.key != key:
            if x.key < key:
                x = x.right
            else:
                x = x.left
        return x

    def delete(self, key):
        z = self.find(key)
        y = self.successor(z) if z.left and z.right else z
        x = y.left if y.left else y.right

        if x:
            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.key = y.key

    def successor(self, x):
        if x.right:
            return self.minimum(x.right)
        y = x.parent
        while y and x == y.right:
            x = y
            y = y.parent
        return y

    def minimum(self, x):
        while x.left:
            x = x.left
        return x

    def print(self):
        print('', ' '.join(map(str, self.root.inwalk())))
        print('', ' '.join(map(str, self.root.prewalk())))


if __name__ == "__main__":
    tree = Tree()
    node_num = int(input())
    for _ in range(node_num):
        command, *value = input().split()
        if "insert" == command:
            tree.insert(int(value[0]))
        elif "find" == command:
            print('yes' if tree.find(int(value[0])) else 'no')
        elif "delete" == command:
            tree.delete(int(value[0]))
        elif "print" == command:
            tree.print()
        else:
            pass

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

parent_node = None

        
def getParent():
    tmp_node = Nodes
    while Nodes.parent != None:
        tmp_node = tmp_node.parent
    return tmp_node    

def printPreorder(u):
    if u == None:
        return
    print(" ", u.key, sep="", end="")
    printPreorder(u.left)
    printPreorder(u.right)
    
def printInorder(u):
    if u == None:
        return
    printInorder(u.left)
    print(" ", u.key, sep="", end="")
    printInorder(u.right)

def find(u, num):
    while u != None and u.key != num:
        if num < u.key:
            u = u.left
        else:
            u = u.right
    if u != None:
        print("yes")
    else:
        print("no")

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

def getSuccessor(u):
    if u.right != None:
        return getMinimum(u.right)
    
    y = u.parent
    while y != None and u == y.right:
        u = y
        y = y.parent
    return y
        
def delete(u, num):
    while u != None and u.key != num:
        if num < u.key:
            u = u.left
        else:
            u = u.right
            
    y = None
    if u.left == None or u.right == None:
        y = u
    else:
        y = getSuccessor(u)
    
    x = None
    if y.left != None:
        x = y.left
    else:
        x = y.right
    
    if x != None:
        x.parent = y.parent
    
    if y.parent == None:
        parent_node = x
    elif y == y.parent.left:
        y.parent.left = x
    else:
        y.parent.right = x
    
    if y != u:
        u.key = y.key
    
n = int(input())


Nodes = []
for i in range(n):
    tmp_node = Node(0)
    Nodes.append(tmp_node)

for i in range(n):
    cmd = input().split()
    if cmd[0] == 'insert':
        key = int(cmd[1])

        insert_node = Nodes[i]
        insert_node.key = key
        key_parent = None
        x = parent_node
            
        while x != None:
            key_parent = x
            if insert_node.key < x.key:
                x = x.left
            else:
                x = x.right
        insert_node.parent = key_parent
            
        if key_parent == None:
            parent_node = insert_node
        elif insert_node.key < key_parent.key:
            key_parent.left = insert_node
        else:
            key_parent.right = insert_node
    
    elif cmd[0] == 'print':
        printInorder(parent_node)
        print("")
        printPreorder(parent_node)
        print("")
    
    elif cmd[0] == 'find':
        key = int(cmd[1])
        find(parent_node, key)
    
    else:
        key = int(cmd[1])
        delete(parent_node, key)

Solution (Python):
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())