binary search tree deletion

algorithm
c-plus-plus
codechef

#1

can anyone give me pseudo code for deletion of two child node in binary search tree.please explain it also.any example will be great.
reply soon
thanks in advance


#2
Procedure :
 1. At first locate the node to be deleted.
  1. If the node is a leaf node :
    i. If the node is left child of the parent , make null the left pointer of its parent node and free the space for the node.
    ii. If the node is right child of the parent , make null the right pointer of its parent node and free the space for the node.

  2. If the node has one child
    i. If the node to be deleted is a left chile of its parent , then make link between the left pointer of its parent node and the child node to be deleted. Then delete the node.
    ii.If the node to be deleted is a right child of its parent , then make link between the right pointer of its parent node and the child node to be deleted. Then delete the node.

  3. If the node to be deleted has two child :
    i. Locate the node with maximum value from the left sub-tree of the node to be deleted.
    ii. Replace the node value to be deleted by the node found in step 4(i)

  4. Now we get updated output


C++ implementation :

node* Delete(node *root, int data)
{
if(root == NULL) return root;

else if(data < root->data) root->left = Delete(root->left,data);

else if (data > root->data) root->right = Delete(root->right,data);

else
{
///Case 1: No child
if(root->left == NULL && root->right == NULL)
{
delete root;
root = NULL;
}

///Case 2: One child
else if(root->left == NULL)
{
struct node *temp = root;
root= root->right;
delete temp;
}

else if(root->right == NULL)
{
struct node *temp = root;
root = root->left;
delete temp;
}

///case 3: 2 children
else
{
node *temp = FindMin(root->right);
root->data = temp->data;
root->right = Delete(root->right,temp->data);
}
}
return root;
}