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 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 == None:
            self.root = z
        elif z.key < y.key:
            y.left = z
        else:
            y.right = z

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

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

    def delete(self, k):
        z = self.find(tree.root, k)
        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 == 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

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

tree = Tree()
n = int(input())
for i in range(n):
    com = input().split()
    if com[0] == "insert":
        tree.insert(int(com[1]))
    elif com[0] == "find":
        ans = tree.find(tree.root, int(com[1]))
        if ans != None:
            print("yes")
        else:
            print("no")
    elif com[0] == "delete":
        tree.delete(int(com[1]))
    else:
        tree.print()

Solution (Python):
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 == None:
            self.root = z
        elif z.key < y.key:
            y.left = z
        else:
            y.right = z

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

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

    def delete(self, k):
        z = self.find(tree.root, k)
        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 == 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)

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

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

tree = Tree()
n = int(input())
for i in range(n):
    com = input().split()
    if com[0] == "insert":
        tree.insert(int(com[1]))
    elif com[0] == "find":
        ans = tree.find(tree.root, int(com[1]))
        if ans != None:
            print("yes")
        else:
            print("no")
    elif com[0] == "delete":
        tree.delete(int(com[1]))
    else:
        tree.print()

Solution (Python):
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 == None:
            self.root = z
        elif z.key < y.key:
            y.left = z
        else:
            y.right = z

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

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

    def delete(self, k):
        z = self.find(tree.root, k)
        y = self.minimum(z.right) 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 == 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 minimum(self, x):
        while x.left:
            x = x.left
        return x

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

tree = Tree()
n = int(input())
for i in range(n):
    com = input().split()
    if com[0] == "insert":
        tree.insert(int(com[1]))
    elif com[0] == "find":
        ans = tree.find(tree.root, int(com[1]))
        if ans != None:
            print("yes")
        else:
            print("no")
    elif com[0] == "delete":
        tree.delete(int(com[1]))
    else:
        tree.print()

Solution (Python):
import sys

class BinarySearchTree:
    class Node:
        __slots__ = ('value', 'left', 'right')

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

        def has_left(self):
            return self.left is not None

        def has_right(self):
            return self.right is not None

        def __str__(self):
            return str(self.value)

    def __init__(self):
        self.root = None

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

        node = self.root
        while True:
            if node.value > value:
                if node.has_left():
                    node = node.left
                else:
                    node.left = self.Node(value)
                    break
            else:
                if node.has_right():
                    node = node.right
                else:
                    node.right = self.Node(value)
                    break

    def find(self, value):
        if self.root is None:
            return False

        node = self.root
        while True:
            if node.value > value:
                if node.has_left():
                    node = node.left
                else:
                    return False
            elif node.value < value:
                if node.has_right():
                    node = node.right
                else:
                    return False
            else:
                return True

    def delete(self, value):
        def _delete(node):
            if not node.has_left():
                right = node.right
                node.right = None
                return right
            elif not node.has_right():
                left = node.left
                node.left = None
                return left
            elif not node.right.has_left():
                right = node.right
                right.left = node.left
                node.left = None
                node.right = None
                return right
            else:
                repl = node.right
                while repl.has_left() and repl.left.has_left():
                    repl = repl.left

                left = repl.left
                node.value = left.value
                repl.left = left.right
                left.right = None
                return node

        if self.root is None:
            return
        elif self.root.value == value:
            self.root = _delete(self.root)
            return

        node = self.root
        while True:
            if node.value > value:
                if not node.has_left():
                    break
                if node.left.value == value:
                    node.left = _delete(node.left)
                    break
                else:
                    node = node.left
            elif node.value < value:
                if not node.has_right():
                    break
                if node.right.value == value:
                    node.right = _delete(node.right)
                    break
                else:
                    node = node.right
            else:
                raise Exception('should not reached')

    def preorder(self):
        def _preorder(node):
            yield node
            if node.has_left():
                yield from _preorder(node.left)
            if node.has_right():
                yield from _preorder(node.right)
        if self.root is not None:
            yield from _preorder(self.root)

    def inorder(self):
        def _inorder(node):
            if node.has_left():
                yield from _inorder(node.left)
            yield node
            if node.has_right():
                yield from _inorder(node.right)
        if self.root is not None:
            yield from _inorder(self.root)

    def postorder(self):
        def _postorder(node):
            if node.has_left():
                yield from _postorder(node.left)
            if node.has_right():
                yield from _postorder(node.right)
            yield node
        if self.root is not None:
            yield from _postorder(self.root)


def run():
    _ = int(input())
    tree = BinarySearchTree()

    for line in sys.stdin:
        if line.startswith('insert'):
            tree.insert(int(line[7:]))
        elif line.startswith('find'):
            if tree.find(int(line[5:])):
                print("yes")
            else:
                print("no")
        elif line.startswith('delete'):
            tree.delete(int(line[7:]))
        elif line.startswith('print'):
            print(' {}'.format(' '.join([str(n) for n in tree.inorder()])))
            print(' {}'.format(' '.join([str(n) for n in tree.preorder()])))
        else:
            raise ValueError('invalid command')


if __name__ == '__main__':
    run()

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

root=None


def PreorderTreeWalk(u):
    if u == None:
        return
    print(" %d"%u.key,end='')
    PreorderTreeWalk(u.left)
    PreorderTreeWalk(u.right)


def InorderTreeWalk(u):
    if (u == None):
        return
    InorderTreeWalk(u.left)
    print(" %d"%u.key,end='')
    InorderTreeWalk(u.right)



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



def treeMinimum(x):
    while (x.left != None):
        x = x.left;
    return x






def treeSuccessor(x) :
    if (x.right != None):
        return treeMinimum(x.right)

    y = x.parent;
    
    if x==y.left:
        return y
    else:
        while (y != None and x == y.right) :
            x = y
            x = y.parent
    
    return y


def treeDelete(z) :
        
        
        
    if (z.left == None or z.right == None):
        y = z
    else:
        y = treeSuccessor(z)

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

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

    
    if (y.parent == None):
        root = x
    else:
        if (y == y.parent.left):
            y.parent.left = x
        else:
            y.parent.right = x
    

    
    if (y != z):
        z.key = y.key;



n=int(input())
s=[]
for i in range(n):
    s=[x for x in input().split()]
    if s[0][0]=='i':
        insert(int(s[1]))    
    elif s[0][0]=='f':
        f = find(root,int(s[1]));
        if (f != None):
            print("yes")
        else:
            print("no")
    elif s[0][0]=='d':
            treeDelete(find(root, int(s[1])));
    else:
        InorderTreeWalk(root)
        print()
            
        PreorderTreeWalk(root)
        print()

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

    def get_child_num(self):
        num = 0
        if self.left != None: num += 1
        if self.right != None: num += 1
        return num

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

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

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

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

    def insert(self, val):
        y = None
        x = self.root
        while x != None:
            y = x
            if val < x.val:
                x = x.left
            else:
                x = x.right
        node = BinaryTreeNode(val=val, parent=y)

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

    def find(self, val):
        x = self.root
        while x != None:
            if x.val == val:
                return x
            elif x.val < val:
                x = x.right
            else:
                x = x.left
        return None

    def delete(self, val):
        z = self.find(val)
        if z == None: return

        y = None
        if z.get_child_num() < 2:
            y = z
        else:
            y = z.get_successor()

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

        if y != z:
            z.val = y.val

    def preorder(self):
        self.preorder_list = []
        self.preorder_bfs(self.root)
        return self.preorder_list

    def preorder_bfs(self, u):
        if u == None: return
        self.preorder_list.append(u.val)
        self.preorder_bfs(u.left)
        self.preorder_bfs(u.right)

    def inorder(self):
        self.inorder_list = []
        self.inorder_dfs(self.root)
        return self.inorder_list

    def inorder_dfs(self, u):
        if u == None: return
        self.inorder_dfs(u.left)
        self.inorder_list.append(u.val)
        self.inorder_dfs(u.right)

def print_elements(arr):
    print(' ' + ' '.join([str(item) for item in arr]))

m = int(input())
bst = BinarySearchTree()
for i in range(m):
    op = input()
    if op.startswith('insert'):
        num = int(op[7:])
        bst.insert(num)
    elif op.startswith('delete'):
        num = int(op[7:])
        bst.delete(num)
    elif op.startswith('find'):
        num = int(op[5:])
        if bst.find(num):
            print('yes')
        else:
            print('no')
    else:
        print_elements(bst.inorder())
        print_elements(bst.preorder())

Solution (Python):
class Tree:
    def __init__(self, orders):
        self.root = None
        for order in orders:
            if len(order) == 1:
                self.inorder_print()
                self.preorder_print()
            else:
                fchr = order[0][0]
                key = int(order[1])
                if fchr == 'f':
                    self.find(key)
                elif fchr == 'i':
                    self.insert(key)
                else:
                    self.delete(key)

    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 not y:
            self.root = z
        elif z.key < y.key:
            y.left = z
        else:
            y.right = z

    def find(self, key):
        x = self.root
        while True:
            if key == x.key:
                print('yes')
                break
            elif key < x.key:
                if x.left:
                    x = x.left
                else:
                    print('no')
                    break
            else:
                if x.right:
                    x = x.right
                else:
                    print('no')
                    break

    def delete(self, key):
        z = self.root
        while z.key != key:
            if key < z.key:
                z = z.left
            else:
                z = z.right

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

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

        if x:
            x.parent = y.parent

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

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

        del (y)

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

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

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

    def inorder_print(self):
        self.root.inorder_print()
        print()

    def preorder_print(self):
        self.root.preorder_print()
        print()


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

    def inorder_print(self):
        if self.left:
            self.left.inorder_print()
        print(' {}'.format(self.key), end='')
        if self.right:
            self.right.inorder_print()

    def preorder_print(self):
        print(' {}'.format(self.key), end='')
        if self.left:
            self.left.preorder_print()
        if self.right:
            self.right.preorder_print()


if __name__ == '__main__':
    import sys
    m = int(input())
    orders = [line.strip().split() for line in sys.stdin]
    Tree(orders)

Solution (Python):
class NullNode():
    def __init__(self):
        self.id = None

null_node = NullNode()
class Node():
    def __init__(self, id):
        global null_node
        self.id = id
        self.parent = null_node
        self.left = null_node
        self.right =  null_node

def preorder(node, out_list=[]):
    if node.id is not None:
        out_list.append(str(node.id))
        out_list = preorder(node.left, out_list)
        out_list = preorder(node.right, out_list)
    return out_list

def inorder(node, out_list=[]):
    if node.id is not None:
        out_list = inorder(node.left, out_list)
        out_list.append(str(node.id))
        out_list = inorder(node.right, out_list)
    return out_list

def insert(node, root_node):
    temp_node_parent = root_node.parent
    temp_node = root_node

    while temp_node.id is not None:
        temp_node_parent = temp_node
        if node.id < temp_node.id:
            temp_node = temp_node.left
        else:
            temp_node = temp_node.right

    node.parent = temp_node_parent
    if node.id < temp_node_parent.id:
        temp_node_parent.left = node
    else:
        temp_node_parent.right = node

def find(id,root_node):
    node = root_node
    while node.id is not None:
        if id < node.id:
            node = node.left
        elif id > node.id:
            node = node.right
        else:
            print('yes')
            break
    else:
        print('no')

def get_successor(node):
    successor = node.right
    while(successor.left.id is not None):
        successor = successor.left
    return successor

def delete(id, root_node):
    global null_node
    node = root_node
    while node.id != id:
        if id < node.id:
            node = node.left
        else:
            node = node.right

    if node.left.id is None or node.right.id is None:
        del_node = node

    else:
        del_node = get_successor(node)
        node.id = del_node.id

    if del_node.left.id is not None:
        change_node = del_node.left
    else:
        change_node = del_node.right

    if change_node.id is not None:
        change_node.parent = del_node.parent

    if del_node.parent.id is None:
        root_node = change_node
    elif del_node.id == del_node.parent.left.id:
        del_node.parent.left = change_node
    else:
        del_node.parent.right = change_node




import sys

n = int(sys.stdin.readline())
input_lines = sys.stdin.readlines()
root_node = NullNode()
for i in range(n):
    input_line = input_lines[i].split()
    command = input_line[0]
    if command == 'insert':
        id = int(input_line[1])
        id_node = Node(id)
        if root_node.id is None:
            root_node = id_node
        else:
            insert(id_node, root_node)

    elif command == 'find':
        id = int(input_line[1])
        find(id, root_node)

    elif command == 'delete':
        id = int(input_line[1])
        delete(id, root_node)
    else:
        inorder_list = inorder(root_node, [])
        preorder_list = preorder(root_node, [])
        out = ' ' + ' '.join(inorder_list)
        print(out)
        out = ' ' + ' '.join(preorder_list)
        print(out)

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

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

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

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


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

    def insert(self, k):
        z = Node(k)
        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 print(self):
        print('', ' '.join(map(str, self.root.inorder())))
        print('', ' '.join(map(str, self.root.preorder())))

    def find(self, k):
        if self.root is None:
            return None
        else:
            return self.root.find(k)

    def delete(self, k):
        z = self.find(k)
        if z.left is None:
            self.transparent(z, z.right)
        elif z.right is None:
            self.transparent(z, z.left)
        else:
            y = self.minimum(z.right)
            if y.parent != z:
                self.transparent(y, y.right)
                y.right = z.right
                y.right.parent = y
            self.transparent(z, y)
            y.left = z.left
            y.left.parent = y

    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 maximum(self, x):
        while x.right:
            x = x.right
        return x

    def transparent(self, u, v):
        if u.parent is None:
            self.root = v
        elif u == u.parent.left:
            u.parent.left = v
        else:
            u.parent.right = v
        if v:
            v.parent = u.parent


m = int(input())
tree = Tree()
for _ in range(m):
    s = input().split()
    if s[0] == "insert":
        tree.insert(int(s[1]))
    elif s[0] == "find":
        if tree.find(int(s[1])):
            print("yes")
        else:
            print("no")
    elif s[0] == "delete":
        tree.delete(int(s[1]))
    else:
        tree.print()

Solution (Python):

N = int(input())
trees = [list(input().split()) for i in range(N)]

class BinaryTree:
    def __init__(self,key,p=None,l=None,r=None):
        self.key = key
        self.p = p
        self.l = l
        self.r = r

def Insert(root,z):
    y = None
    x = root
    while x != None:
        y = x
        if z.key < x.key:
            x = x.l
        else:
            x = x.r
    z.p = y

    if y == None:
        root = z
    elif z.key < y.key:
        y.l = z
    else:
        y.r = z
    return root

def preOrder(x):
    if x == None:
        return
    global preList
    preList.append(x.key)
    
    preOrder(x.l)
    preOrder(x.r)

def inOrder(x):
    if x == None:
        return
    inOrder(x.l)

    global inList
    inList.append(x.key)
    
    inOrder(x.r)

def Find(x,z):
    while x != None and z.key != x.key:
        y = x
        if z.key < x.key:
            x = x.l
        else:
            x = x.r
    return x


def Delete(x, z):
    if z.l == None or z.r == None:
        y = z
    else:
        y = getSuccessor(z)

    if y.l != None:
        x = y.l
    else:
        x = y.r

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

    if y.p == None:
        global root
        root = x
    elif y == y.p.l:
        y.p.l = x
    else:
        y.p.r = x
    if y != z:
        z.key = y.key
        
def getSuccessor(x):
    if x.r != None:
        return getMinimum(x.r)
    y = x.p
    while y != None and x == y.r:
        x = y
        y = y.p
    return y

def getMinimum(x):
    while x.l != None:
        x = x.l
    return x

root = None
for data in trees:
    if data[0] == "print":
        inList = []
        preList = []
        inOrder(root)
        a = " " + " ".join([str(num) for num in inList])
        print(a)

        preOrder(root)
        a = " " + " ".join([str(num) for num in preList])
        print(a)

    else:
        z = BinaryTree(int(data[1]))
        if data[0] == "insert":
            root = Insert(root,z)
        elif data[0] == "find":
            a = Find(root, z)
            if a == None:
                print("no")
            else:
                print("yes")
        elif data[0] == "delete":
            Delete(root, Find(root,z))