binary search tree deletion

general
, ,
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

1 Like
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 : 
----------
<!-- 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>