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
``` Procedure : 1. At first locate the node to be deleted.
-
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. -
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. -
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) -
Now we get updated output
----------
C++ implementation :
----------
<!-- generated by C/C++ to HTML Formatter -->
<div style="background-color: rgb(243, 243, 243); font-family: fixed,monospace; border: 1px solid rgb(200, 200, 200); color: RGB(0, 0, 0);"><div style="margin: 10px"> node* Delete(node *root, <span style="color: rgb(7, 55, 99); font-weight: bold">int</span> data)
{
<span style="color: rgb(7, 55, 99); font-weight: bold">if</span>(root == NULL) <span style="color: rgb(7, 55, 99); font-weight: bold">return</span> root;
<span style="color: rgb(7, 55, 99); font-weight: bold">else</span> <span style="color: rgb(7, 55, 99); font-weight: bold">if</span>(data < root->data) root->left = Delete(root->left,data);
<span style="color: rgb(7, 55, 99); font-weight: bold">else</span> <span style="color: rgb(7, 55, 99); font-weight: bold">if</span> (data > root->data) root->right = Delete(root->right,data);
<span style="color: rgb(7, 55, 99); font-weight: bold">else</span>
{
<span style="color: rgb(56, 118, 29); font-style: italic">///Case 1: No child</span>
<span style="color: rgb(7, 55, 99); font-weight: bold">if</span>(root->left == NULL && root->right == NULL)
{
<span style="color: rgb(7, 55, 99); font-weight: bold">delete</span> root;
root = NULL;
}
<span style="color: rgb(56, 118, 29); font-style: italic">///Case 2: One child</span>
<span style="color: rgb(7, 55, 99); font-weight: bold">else</span> <span style="color: rgb(7, 55, 99); font-weight: bold">if</span>(root->left == NULL)
{
<span style="color: rgb(7, 55, 99); font-weight: bold">struct</span> node *temp = root;
root= root->right;
<span style="color: rgb(7, 55, 99); font-weight: bold">delete</span> temp;
}
<span style="color: rgb(7, 55, 99); font-weight: bold">else</span> <span style="color: rgb(7, 55, 99); font-weight: bold">if</span>(root->right == NULL)
{
<span style="color: rgb(7, 55, 99); font-weight: bold">struct</span> node *temp = root;
root = root->left;
<span style="color: rgb(7, 55, 99); font-weight: bold">delete</span> temp;
}
<span style="color: rgb(56, 118, 29); font-style: italic">///case 3: 2 children</span>
<span style="color: rgb(7, 55, 99); font-weight: bold">else</span>
{
node *temp = FindMin(root->right);
root->data = temp->data;
root->right = Delete(root->right,temp->data);
}
}
<span style="color: rgb(7, 55, 99); font-weight: bold">return</span> root;
}</div></div>