delete.py

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

#I can use this method to traverse a tree using the inorder approach
def inOrderBinaryTreeTraversal(a):
    if(not a):
        return
    inOrderBinaryTreeTraversal(a.left)
    print(a.data, end = " ")
    inOrderBinaryTreeTraversal(a.right)
  

  
# function to delete element in binary tree
def remove(passedRoot, key):
    if passedRoot == None :
        return None
    if passedRoot.left == None and passedRoot.right == None:
        if passedRoot.key == key :
            return None
        else :
            return passedRoot
    key_node = None
    r = []
    r.append(passedRoot)
    temp = None
    while(len(r)):
        temp = r.pop(0)
        if temp.data == key:
            key_node = temp
        if temp.left:
            r.append(temp.left)
        if temp.right:
            r.append(temp.right)
    if key_node :
        b = temp.data
    # deleteDeepest(passedRoot,temp)
        key_node.data = b
    return passedRoot
  
# I can simulate deletion using this code block. key represents the key to the value i want to delete
if __name__=='__main__':
    #assigning root node
    root = Node(9)
#     assigning branches
    root.left = Node(10)
    root.right = Node(8)
    
    root.right.left = Node(14)
    root.right.left.right = Node(15)
    root.right.left.left = Node(16)
    root.right.right = Node(7)
    root.left.right = Node(11)
    root.left.left = Node(6)
    print("The tree before the deletion:")
    inOrderBinaryTreeTraversal(root)
    key = 6
    root = remove(root, key)
    print()
    print("The tree after the deletion;")
    inOrderBinaryTreeTraversal(root)