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

**Delete a leaf node:**We will unlink the node from its parent node and delete the node.**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.**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.

## Leave a Reply