Segmentation fall is received when root node is deleted

[techie929]

//when I delete root node from bst the below code is showing segmentation fault,Please tell where should I change the code

void BinarySearchTree::remove(char* d)
{
    //Locate the element
    bool found = false;
    if(isEmpty())
    {
        cout<<" This Tree is empty! "<<endl;
        return;
    }
    tree_node* curr;
    tree_node* parent;
    curr = root;
    while(curr != NULL)
    {
         if(strcmp(curr->data,d)==0)
         {
            found = true;
            break;
         }
         else
         {
             parent = curr;
             if(strcmp(d,curr->data)>0) curr = curr->right;
             else curr = curr->left;
         }
    }
    if(!found)
{
        cout<<" Data not found! "<<endl;
        exit(1);
    }


// 3 cases :
    // 1. We're removing a leaf node
    // 2. We're removing a node with a single child
    // 3. we're removing a node with 2 children

    // Node with single child
    if((curr->left == NULL && curr->right != NULL)|| (curr->left != NULL
&& curr->right == NULL))
    {
       if(curr->left == NULL && curr->right != NULL)
       {
           if(parent->left == curr)
           {
             parent->left = curr->right;
             delete curr;
           }
           else
           {
             parent->right = curr->right;
             delete curr;
           }
       }
       else // left child present, no right child
       {
          if(parent->left == curr)
           {
             parent->left = curr->left;
             delete curr;
           }
           else
           {
             parent->right = curr->left;
             delete curr;
           }
       }
     return;
    }

//We're looking at a leaf node
if( curr->left == NULL && curr->right == NULL)
    {
        if(parent->left == curr) parent->left = NULL;
        else parent->right = NULL;
delete curr;
return;
    }


    //Node with 2 children
    // replace node with smallest value in right subtree
    if (curr->left != NULL && curr->right != NULL)
    {
        tree_node* chkr;
        chkr = curr->right;
        if((chkr->left == NULL) && (chkr->right == NULL))
        {
            curr = chkr;
            delete chkr;
            curr->right = NULL;
        }
        else // right child has children
        {
            //if the node's right child has a left child
            // Move all the way down left to locate smallest element

            if((curr->right)->left != NULL)
            {
                tree_node* lcurr;
                tree_node* lcurrp;
                lcurrp = curr->right;
                lcurr = (curr->right)->left;
                while(lcurr->left != NULL)
                {
                   lcurrp = lcurr;
                   lcurr = lcurr->left;
                }
strcpy(curr->data,lcurr->data);
                delete lcurr;
                lcurrp->left = NULL;
           }
           else
           {
               tree_node* tmp;
               tmp = curr->right;
               strcpy(curr->data,tmp->data);
   curr->right = tmp->right;
               delete tmp;
           }

        }
return;
    }

}

[VernonDozier]

You need to find out exactly where, when, and under what conditions this seg fault happens. There's more than one way to program a binary search tree. I would have the search and delete functions separate. You are searching inside your delete function. I don't think you should do that. Search functions should search. Delete functions should delete.

Anyway, if a node is a root node, it's parent will be NULL, so make sure you check for the parent being NULL before trying to do something like parent->right . If you do, that's a seg fault. That's why you need to find the exact line that it happens.

[thomas_naveen]

Try using a debugger like gdb to identify the exact crash and the reason.

[mitrmkar]

//when I delete root node from bst

line 29: declares tree_node* parent (and leaves it uninitialized)

Then, if the root node will be a match for the data you search for, you end up using the uninitialized pointer from line 44 onwards.

[techie929]

If the parent is NULL,I tried to do something like this,still its not working:

if(parent==NULL)
{
delete curr;
return
}

[VernonDozier]

If the parent is NULL,I tried to do something like this,still its not working:

if(parent==NULL)
{
delete curr;
return
}

Be more specific than "it's not working". That could mean anything. It's not going to work. Any deletion is almost always going to involve more than that. Draw it out on paper, with arrows. What do you need to do to delete the root node? Then turn that into code. If you delete the root node and don't do anything else, how can you ever find the top of the tree again?