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