Delete a Node in Binary Search Tree (BST)

Deletion in BST:

1) Node to be deleted is leaf:

  Simply remove from the tree.

              80                                    80

           /     \         delete(50)     /   \

          60      100       --------->   60     100

         /  \    /  \                          \      /  \

       50   70  90   110                    70   90   110

2) Node to be deleted has only one child:

  Swap the child to the node and delete the new child.

              80                                     80

           /     \         delete(60)      /   \

          60      100       --------->     70     100

            \    /  \                                 /  \

            70  90   110                           90   110

3) Node to be deleted has both children:

 A. Find inorder successor of the node.

 B. Copy contents of the inorder successor to the node and delete the inorder successor.   

     (Inorder predecessor can also be used).

              80                                     90

           /     \         delete(80)      /   \

          70      100       --------->     70    100

                  /   \                                      \

                90   110                                     110

Note: Inorder successor is needed only when right child is not empty.

Inorder successor can be obtained as the minimum value in right sub tree of the node.