# 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.