Binary search tree deletion

A Binary Search tree is generated by inserting in order the following integers: 50, 12, 62, 5, 20, 58, 91, 3, 8, 37, 60, 24. Show the result binary search tree after the elements have been deleted in the order 20, 12, 37, 5, 62, 50, 8.

Three possible cases occur when we delete an element of a Binary Search Tree. Deletion of an element should preserve the BST property.

Let the node to be deleted be x.

Case  1: x has no children.

             Delete x by making parent of x point to NULL. Parent of x can be obtained through a trailing pointer.

Case 2: x has one child.

             Delete x by making parent of x point to x's child, then delete x.

The case 1 and case 2 are simpler compared to the third case, case 3 is a bit trickier.

Case 3: x has two children.

            To preserve the binary search tree property we need to copy the immediate successor of x to x's place. The immediate successor of x can be found in right subtree of x. The immediate successor is also the minimum element in the right subtree of x.  Let the immediate successor be y. First we need to search this minimum element y. After we have copied y to x's place, we will have a binary search tree (and the BST property preserved) with duplicates.  y element is at two places and we need to delete the y in the original place. Deleting the y in original place will be either case 1 or case 2.  Deleting y in the original place cannot be case 3 because it is the minimum element in a binary search tree subtree, the minimum element has always one child or no child.          

Searching the minimum element in right subtree involves traversing the left pointers from the root node of the subtree. The last non NULL node gives the minimum element in the right subtree of x.

Briefly, copy the minimum element y in the right subtree of x to x's place. Delete the y in original place through case 1 or case 2.

The Binary Search tree is generated by inserting in order the following integers: 50, 12, 62, 5, 20, 58, 91, 3, 8, 37, 60, 24. Now let us delete the elements in the order 20, 12, 37, 5, 62, 50, 8.

Share your thoughts in the comments below, to make me describe the blog post  even better and do recommend the post if you found the content helpful!!!