Deletion of a Node From Binary Search Tree
In order to delete node from binary search tree we have to consider three possibilities.
(1) A node to be deleted has no sub tree.
(2) A node to be deleted has only one sub tree (left or right).
(3) A node to be deleted has two sub trees (left and right).
Lets consider each possibilities by using following example:
Possibility 1: If a node to be deleted has no sub tree. In such case a node is deleted directly. Suppose we want to delete node 15. Here node 15 has no left or right sub tree so we can delete it directly. After deleting node 15 tree looks like as shown below:
Possibility 2: If a node to be deleted has only one sub tree either left sub tree or right sub tree. In such case the sub tree of the deleted node is linked directly with the parent of the deleted node.
Suppose we want to delete node 35. Here node 35 has one right sub tree so we link this right sub tree with parent of node 35 which is 45. Now the node which we want to link with node 45 is 42 and value of 42 is less than 45 so we link it as a left sub tree of node 45. After deleting node 35 tree looks like as shown below:
Possibility 3: If a node to be deleted has two sub trees left as well as right. In such case we have to perform following steps:
(a) Find in order successor of the node to be deleted.
(b) Append the right sub tree of the in order successor to its grand parent.
(c) Replace the node to be deleted with its in order successor.
Suppose we want to delete node 68. Here node 68 has both left and right sub tree. So first we have to find InOrder successor of node 68 which is 78.
42 45 64 68 78
Now replace the node to be deleted with it’s InOrder successor. So we replace node 68 with node 78. After deleting node 68 tree looks like as shown below: