Deletion Operations on Binary search Tree -

. Deletion – deletion means to remove an element from a tree. Deleting a node from Binary search tree has following three cases...

· Deleting a leaf node (a node with no children)

· Deleting a node with one child

· Deleting a node with two children

Case 1: Deleting a leaf node - We use the following steps to delete a leaf node from BST...

·Step 1: Find the node to be deleted using search operation

·Step 2: Delete the node using free function (If it is a leaf) and terminate the function.

Case 2: Deleting a node with one child -We use the following steps to delete a node with one child from BST...

·Step 1: Find the node to be deleted using search operation

·Step 2: If it has only one child, then create a link between its parent and child nodes.

·Step 3: Delete the node using free function and terminate the function.

·Step 1: Find the node to be deleted using search operation

·Step 2: If it has two children, then find the largest node in its left subtree (OR) the smallest node in its right subtree.

·Step 3: Swap both deleting node and node which found in above step.

·Step 4: Then, check whether deleting node came to case 1 or case 2 else go to steps 2

·Step 5: If it comes to case 1, then delete using case 1 logic.

·Step 6: If it comes to case 2, then delete using case 2 logic.

·Step 7: Repeat the same process until node is deleted from the tree.