//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)
{
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
6
Views
8 Years
Discussion Span
Last Post by 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.

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

//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.

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

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

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?

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.