Insertion and Deletion in a Binary search tree in Python

In this tutorial, we will learn to search, insert and delete nodes of a binary search tree recursively in Python. We will also learn the binary search and inorder tree traversal algorithms. Deletion is a little complex than the searching and insertion since we must ensure that the binary search tree property is properly maintained. Also, Insertion and Deletion are the two important operations in a Binary search tree.

Insertion in Binary search tree ( BST ) in Python

class Tree: 
  
    def __init__(node, value): 
        node.value = value  
        node.left = None
        node.right = None
    
    def Inorder( node, Root ): 
        if( Root is None ): 
            return
        node.Inorder(Root.left) 
        print(Root.value,end = ' ') 
        node.Inorder(Root.right) 
  
    def Insert(node, value): 
        if node is None: 
            node = Tree(value)
        elif value < node.value:
            if node.left is None:
                node.left = Tree(value)
            else:
               node.left.Insert(value) 
        else:
            if node.right is None:
                node.right = Tree(value)
            else:
                node.right.Insert(value)
Root = Tree(6) 
Root.Insert(4) 
Root.Insert(2) 
Root.Insert(5) 
Root.Insert(9) 
Root.Insert(8) 
Root.Insert( 10) 

print ("Inorder traversal after insertion: ",end = '')
Root.Inorder(Root)

Output:

Inorder traversal after insertion: 2 4 5 6 8 9 10

• If the value to be inserted is less than the node, we will traverse its left subtree recursively.
• We traverse the right subtree recursively when the value to be inserted is greater than the node.
• If the node is empty, We will create a node and insert the value.

Deletion in BST in Python

class Tree: 
  
    def __init__(node, value): 
        node.value = value  
        node.left = None
        node.right = None
    
    def Inorder( node, Root ): 
        if( Root is None ): 
            return
        node.Inorder(Root.left) 
        print(Root.value,end = ' ') 
        node.Inorder(Root.right) 
  
    def Insert(node, value): 
        if node is None: 
            node = Tree(value)
        elif value < node.value:
            if node.left is None:
                node.left = Tree(value)
            else:
               node.left.Insert(value) 
        else:
            if node.right is None:
                node.right = Tree(value)
            else:
                node.right.Insert(value)

    def Delete(node,temp, value): 
        if value < node.value:
            temp = node
            node.left.Delete(temp,value)
        elif(value > node.value):
            temp = node
            node.right.Delete(temp, value)
            
        else:
            if (node.left is None and node.right is None):
                if(temp.left == node):
                    temp.left = None
                else:
                    temp.right = None
                node = None
        
            elif node.right is None :
                if(temp.left == node):
                    temp.left = node.left
                else:
                    temp.right = node.left
                node = None
    
            elif node.left is None :
                if(temp.left == node):
                    temp.left = node.right
                else:
                    temp.right = node.right
                node = None
                
            else:
                temp = node.right
                while(temp.left is not None):
                    temp = temp.left 
                node.value = temp.value
                node.right.Delete(temp,temp.value)   
Root = Tree(6) 
Root.Insert(4) 
Root.Insert(2) 
Root.Insert(5) 
Root.Insert(9) 
Root.Insert(8) 
Root.Insert( 10) 
  
print ("Inorder traversal after insertion: ",end = '')
Root.Inorder(Root) 

Root.Delete(Root, 2) 
print ('\n 2 is deleted: ',end ='')
Root.Inorder(Root) 
  
Root.Delete(Root, 4) 
print ('\n 4 is deleted: ',end ='')
Root.Inorder(Root) 
  
Root.Delete(Root, 6) 
print ('\n 6 is deleted: ',end ='')
Root.Inorder(Root)

Output:

Inorder traversal after insertion: 2 4 5 6 8 9 10 
2 is deleted: 4 5 6 8 9 10 
4 is deleted: 5 6 8 9 10 
6 is deleted: 5 8 9 10

To delete a node in a binary search tree, we need to search it. Then we need to find out whether the node has children or not.

1. Delete a leaf node: We will unlink the node from its parent node and delete the node.
2. Delete a node having one child: We will copy the child of the node(left child or right child) and link it to its parent node. At last, we will delete the node.
3. Delete a node having two children: We will find the next highest element in its right subtree. Replace the node to be deleted with its next highest inorder successor and delete its inorder successor duplicate node.

I hope you have understood the code…😊
Recommended concepts to read: Inorder tree traversal, preorder traversal, postorder traversal, and level order traversal.