50 50
/ delete(20) /
30 70 ---------> 30 70
/ / /
20 40 60 80 40 60 80
We have discussed BST search and insert operations. In this post, delete operation is discussed. When we delete a node, three possibilities arise.
1) Node to be deleted is leaf: Simply remove from the tree.
2) Node to be deleted has only one child: Copy the child to the node and delete the child
50 50
/ delete(30) /
30 70 ---------> 40 70
/ /
40 60 80 60 80
3) Node to be deleted has two children: Find inorder successor of the node. Copy contents of the inorder successor to the node and delete the inorder successor. Note that inorder predecessor can also be used.
50 60
/ delete(50) /
40 70 ---------> 40 70
/
60 80 80
The important thing to note is, inorder successor is needed only when right child is not empty. In this particular case, inorder successor can be obtained by finding the minimum value in right child of the node.
Output:
Inorder traversal of the given tree 20 30 40 50 60 70 80 Delete 20 Inorder traversal of the modified tree 30 40 50 60 70 80 Delete 30 Inorder traversal of the modified tree 40 50 60 70 80 Delete 50 Inorder traversal of the modified tree 40 60 70 80
Illustration:
Time Complexity: The worst case time complexity of delete operation is O(h) where h is height of Binary Search Tree. In worst case, we may have to travel from root to the deepest leaf node. The height of a skewed tree may become n and the time complexity of delete operation may become O(n)