Member Avatar for 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;
    }

}
  • 4 Contributors
  • 5 Replies
  • 109 Views
  • 22 Hours Discussion Span
  • Latest Post Latest Post by VernonDozier

Dani AI

Generated

This thread already hits the main suspects: an uninitialized parent pointer, treating the root like any other node, and the suggestion to use a debugger. Build on those leads and check one more deadly pattern that is visible in the posted code: assigning a pointer to a replacement node and then deleting that replacement. That leaves your curr pointing at freed memory and explains the segfaults that show up only when deleting the root or certain two-child cases.

Concrete checklist to fix and verify:

  • Initialize parent to NULL before the search. When you find the node, detect parent == NULL and handle the root as a special case. Don’t just delete curr; — update the root pointer so the tree still has an entry point.
  • For a node with two children, copy the successor’s data into the target node, then delete the successor node and update the successor’s parent-child link. Never do curr = successor; delete successor; because curr becomes a dangling pointer.
  • If node payloads are char*, check ownership: avoid double-free and buffer-overflow risks. Prefer std::string so copies and lifetime are managed automatically.

Small examples (minimal, illustrative):

struct Node { std::string data; Node* left; Node* right; };

if (parent == NULL) {   // deleting root with single child or leaf
    root = (curr->left) ? curr->left : curr->right;
    delete curr;
    return;
}

Debug workflow:

  • Compile with -g, set a breakpoint around the delete logic and inspect curr/parent with GDB.
  • Run under Valgrind to catch invalid reads/writes and use-case leaks.
  • Test cases one-by-one: leaf, single-child root, single-child non-root, two-children where successor is immediate right child, two-children where successor is deep.

References: GDB docs (GDB manual), Valgrind (valgrind.org), and C++ behavior for delete and std::string (delete semantics, std::string). This should complement , and suggestions and point to the exact logic error to fix.

Recommended Answers

All 5 Replies

Member Avatar for 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.

Member Avatar for thomas_naveen

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

Member Avatar for 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.

Member Avatar for techie929

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

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

Member Avatar for 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?

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.