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 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):
            def get_next(x):
                c = x.left if x.left else x.right
                if c: return get_next(c)
                else: return x
            if z.left and z.right:
                next_node = get_next(z.right)
                z_key_n = next_node.key
                ldelete(next_node)
                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)


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

       

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

Solution (Python):
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:
                c = z.right
                while c:
                    next_node = c
                    c = c.left if c.left else c.right
                z_key_n = next_node.key
                ldelete(next_node)
                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)


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

       

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

Solution (Python):
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):
    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 T[n]
    elif left is None and right is not None:
        x = T[p].index(n)
        T[p][x] = right
        T[right][2] = z[2]
        del T[n]
    elif left is not None and right is None:
        x = T[p].index(n)
        T[p][x] = left
        T[left][2] = z[2]
        del T[n]
    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]
        n_r = T[next_n][1]
        n_p = T[next_n][2]
        if n_r is not None:
            v = T[n_r]
            if v[0] == n:
                v[0] = next_n
            if v[1] == n:
                v[1] = next_n
            if v[2] == n:
                v[2] = next_n
        if n_p is not None:
            v = T[n_p]
            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))

Solution (Python):
import sys

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

    def append_child(self, child):
        if self.key > child.key:
            self.left = child
            child.parent = self
        elif self.key < child.key:
            self.right = child
            child.parent = self
        else:
            raise "cannot append a child with same key"

    def remove(self, tree):
        parent = self.parent
        if self.left and self.right:
            child = self.right
            while child.left is not None:
                child = child.left
            child.remove(tree)
            self.key = child.key
        elif self.left or self.right:
            child = self.left or self.right
            if parent is None: 
                self.root = child
                child.parent = None
            else:
                parent.append_child(child)
        else:
            if parent is None: 
                tree.root = None
            elif self is parent.left:
                parent.left = None
            else:
                parent.right = None

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

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

        node = self.root
        parent = None
        while node is not None:
            if x > node.key:
                parent = node
                node = node.right
            elif x < node.key:
                parent = node
                node = node.left
            else:
                return node

        parent.append_child(inserted)
        return inserted

    def delete(self, x):
        deleted = self.find(x)
        if deleted is None:
            return False
        deleted.remove(self)
        return True

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

    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)


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.delete(int(command[1]))
    else:
        raise 'unknown command: ' + command[0]

Solution (Python):

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
        elif t.left.left!=None and t.left.right==None:
            t.left=t.left.left
        else:
            a=newPoint(t.left.right)
            Delete(t,a)
            t.left.n=a
    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
        elif t.right.left!=None and t.right.right==None:
            t.right=t.right.left
        else:
            a=newPoint(t.right.right)
            Delete(t,a)
            t.right.n=a
    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 newPoint(t):
    if t.left!=None:
        a=newPoint(t.left)
    else:
        a=t.n
    return a
        

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)

Solution (Python):



"""
input:
10
insert 30
insert 88
insert 12
insert 1
insert 20
find 12
insert 17
insert 25
find 16
print

output: finded + in_order + pre_order
yes
no
 1 12 17 20 25 30 88
 30 12 1 20 17 25 88

"""

import sys


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

    def insert(self, data):
        """
        insert data according to BST rules
        """
        if data < self.data:
            if not self.left:
                self.left = Node(data)
            else:
                self.left.insert(data)
        
        else:
            if not self.right:
                self.right = Node(data)
            else:
                self.right.insert(data)

        return self.data

    def find(self, data, parent=None):
        """
        find node with given data
        tree walk as insert goes
        """
        if data < self.data:
            if not self.left:
                return None, None
            return self.left.find(data=data, parent=self)
        elif data > self.data:
            if not self.right:
                return None, None
            return self.right.find(data=data, parent=self)
        else:
            return self, parent

    def children_count(self):
        """
        for choosing node deleting strategy
        """
        cnt = 0
        if self.left:
            cnt += 1
        if self.right:
            cnt += 1
        return cnt

    def delete(self, data):
        """
        delete node with given data
        """
        node, parent = self.find(data)
        if node:
            children_count = node.children_count()
            if children_count == 0:
                
                if parent.left is node:
                    parent.left = None
                else:
                    parent.right = None
                del node
            elif children_count == 1:
                
                if node.left:
                    n = node.left
                else:
                    n = node.right
                if parent:
                    if parent.left is node:
                        parent.left = n
                    else:
                        parent.right = n
                del node
            else:
                parent = node
                successor = node.right
                while successor.left:
                    parent = successor
                    successor = successor.left
                
                node.data = successor.data
                if parent.left == successor:
                    parent.left = successor.right
                else:
                    parent.right = successor.right
                del node


def pre_order(node):
    if node:
        print('', node.data, end='')
        pre_order(node.left)
        pre_order(node.right)
    return None


def in_order(node):
    if node:
        in_order(node.left)
        print('', node.data, end='')
        in_order(node.right)
    return None


def action(command, content):
    
    if command.startswith('in'):
        tree_root.insert(int(content))

    elif command.startswith('fi'):
        if tree_root.find(int(content)) == (None, None):
            print('no')
        else:
            print('yes')

    elif command.startswith('de'):
        tree_root.delete(int(content))
    
    else:
        in_order(tree_root)
        print('')
        pre_order(tree_root)
        print('')

    return None


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    array_length = int(_input[0])
    command_list = list(map(lambda x: x.split(), _input[1:]))
    

    flag, tree_root = False, None
    for each in command_list:
        command, content = each[0], each[-1]
        if (not flag) and command.startswith('in'):
            tree_root = Node(data=int(content))
            flag = True
            continue
        action(command, content)

Solution (Python):



"""
input:
10
insert 30
insert 88
insert 12
insert 1
insert 20
find 12
insert 17
insert 25
find 16
print

output: finded + in_order + pre_order
yes
no
 1 12 17 20 25 30 88
 30 12 1 20 17 25 88

"""

import sys


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

    def insert(self, data):
        """
        insert data according to BST rules
        """
        if data < self.data:
            if not self.left:
                self.left = Node(data)
            else:
                self.left.insert(data)
        
        else:
            if not self.right:
                self.right = Node(data)
            else:
                self.right.insert(data)

        return self.data

    def find(self, data, parent=None):
        """
        find node with given data
        tree walk as insert goes
        """
        if data < self.data:
            if not self.left:
                return None, None
            return self.left.find(data=data, parent=self)
        elif data > self.data:
            if not self.right:
                return None, None
            return self.right.find(data=data, parent=self)
        else:
            return self, parent

    def children_count(self):
        """
        for choosing node deleting strategy
        """
        cnt = 0
        if self.left:
            cnt += 1
        if self.right:
            cnt += 1
        return cnt

    def delete(self, data):
        """
        delete node with given data
        """
        node, parent = self.find(data)
        if node:
            children_count = node.children_count()
            if children_count == 0:
                
                if parent.left is node:
                    parent.left = None
                else:
                    parent.right = None
                del node
            elif children_count == 1:
                
                if node.left:
                    n = node.left
                else:
                    n = node.right
                if parent:
                    if parent.left is node:
                        parent.left = n
                    else:
                        parent.right = n
                del node
            else:
                parent = node
                successor = node.right
                
                while successor.left:
                    parent = successor
                    successor = successor.left
                    
                
                node.data = successor.data
                if parent.left == successor:
                    parent.left = successor.right
                else:
                    parent.right = successor.right
                del node


def pre_order(node):
    if node:
        print('', node.data, end='')
        pre_order(node.left)
        pre_order(node.right)
    return None


def in_order(node):
    if node:
        in_order(node.left)
        print('', node.data, end='')
        in_order(node.right)
    return None


def action(command, content):
    
    if command.startswith('in'):
        tree_root.insert(int(content))

    elif command.startswith('fi'):
        if tree_root.find(int(content)) == (None, None):
            print('no')
        else:
            print('yes')

    elif command.startswith('de'):
        tree_root.delete(int(content))
    
    else:
        in_order(tree_root)
        print('')
        pre_order(tree_root)
        print('')

    return None


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    array_length = int(_input[0])
    command_list = list(map(lambda x: x.split(), _input[1:]))
    

    flag, tree_root = False, None
    for each in command_list:
        command, content = each[0], each[-1]
        if (not flag) and command.startswith('in'):
            tree_root = Node(data=int(content))
            flag = True
            continue
        action(command, content)

Solution (Python):



"""
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

output: finded + in_order + pre_order
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

"""

import sys


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

    def insert(self, data):
        """
        insert data according to BST rules
        """
        if data < self.data:
            if not self.left:
                self.left = Node(data)
            else:
                self.left.insert(data)
        
        else:
            if not self.right:
                self.right = Node(data)
            else:
                self.right.insert(data)

        return self.data

    def find(self, data, parent=None):
        """
        find node with given data
        tree walk as insert goes
        """
        if data < self.data:
            if not self.left:
                return None, None
            return self.left.find(data=data, parent=self)
        elif data > self.data:
            if not self.right:
                return None, None
            return self.right.find(data=data, parent=self)
        else:
            return self, parent

    def children_count(self):
        """
        for choosing node deleting strategy
        """
        cnt = 0
        if self.left:
            cnt += 1
        if self.right:
            cnt += 1
        return cnt

    def delete(self, data):
        """
        delete node with given data
        """
        node, parent = self.find(data)
        if node:
            children_count = node.children_count()
            if children_count == 0:
                
                if parent.left is node:
                    parent.left = None
                else:
                    parent.right = None
                del node
            elif children_count == 1:
                
                if node.left:
                    n = node.left
                else:
                    n = node.right
                if parent:
                    if parent.left is node:
                        parent.left = n
                    else:
                        parent.right = n
                del node
            else:
                
                parent = node
                
                
                successor = node.right
                while successor.left:
                    parent = successor
                    successor = successor.left

                
                node.data = successor.data
                
                if parent.left == successor:
                    parent.left = successor.right
                else:
                    parent.right = successor.right
                del successor


def pre_order(node):
    if node:
        print('', node.data, end='')
        pre_order(node.left)
        pre_order(node.right)
    return None


def in_order(node):
    if node:
        in_order(node.left)
        print('', node.data, end='')
        in_order(node.right)
    return None


def action(command, content):
    
    if command.startswith('in'):
        tree_root.insert(int(content))

    elif command.startswith('fi'):
        if tree_root.find(int(content)) == (None, None):
            print('no')
        else:
            print('yes')

    elif command.startswith('de'):
        tree_root.delete(int(content))

    
    else:
        in_order(tree_root)
        print('')
        pre_order(tree_root)
        print('')

    return None


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    array_length = int(_input[0])
    command_list = list(map(lambda x: x.split(), _input[1:]))
    

    flag, tree_root = False, None
    for each in command_list:
        command, content = each[0], each[-1]
        if (not flag) and command.startswith('in'):
            tree_root = Node(data=int(content))
            flag = True
            continue
        action(command, content)