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

def insert(root,node):
    if root is None:
        root=node
    else:
        if root.val>node.val:
            if root.left is None:
                root.left=node
            else:
                insert(root.left,node)
        else:
            if root.right is None:
                root.right=node
            else:
                insert(root.right,node)

def find_min(root,parent):
    if root.left:
        return find_min(root.left,root)
    else:
        return[parent,root]

def del_node(root,val):
    if root.val == val:
        if root.right and root.left:
            [parent,succ] = find_min(root.right,root)
            if parent.left == succ:
                parent.left=succ.right
            else:
                parent.right = succ.right
            succ.left=root.left
            succ.right=root.right
            return succ
        else:
            if root.left:
                return root.left
            if root.right:
                return root.right
    else:
        if root.val>val:
            if root.left:
                root.left=del_node(root.left,val)
        else:
            if root.right:
                root.right=del_node(root.right,val)
        return root

def inorder(root):
    if root:
        inorder(root.left)
        print(root.val)
        inorder(root.right)

def preorder(root):
    if root:
        print(root.val)
        preorder(root.left)
        preorder(root.right)

def postorder(root):
    if root:
        postorder(root.left)
        postorder(root.right)
        print(root.val)

print('Inserting values in a tree')
root=Node(50)
insert(root,Node(30))
insert(root,Node(20))
insert(root,Node(40))
insert(root,Node(70))
insert(root,Node(60))
insert(root,Node(80))

print('pre order traversal')
preorder(root)
print('post order traversal')
postorder(root)


root=del_node(root,80)
print('After deleting')
preorder(root)