Thread: Deleting from a binary search tree

Hello,
I've posted a few topics on these forums and have received a large amount of help. I'm winding up the program, finally, and I've come to a huge snag. The last function I need to get working is deleting a node from a binary search tree. I understand the algorithm but i'm having really big issues implementing it in code.

Here is the code I have, currently:

Code:

void removeTree(TreeT tree, TreeInfoT data)
{
printf("Inside removeTree. Data= %s Node=%s \n",data->name,tree->root->info->name);
deleteNode(tree->root,data);
}

void deleteNode(TreeNodeT root,TreeInfoT data)
{
TreeNodeT ptr=findNode(root,data); //find the node
printf ("inside deleteNode. Pointer from findNode=%s \n",ptr->info->name);
if (ptr->L!=NULL && ptr->R!=NULL) //two children
{
	printf("Entered inside of 'Two Children' if statement \n");
	TreeNodeT max=ptr->L; //set a pointer, max, to the node in the left tree to prepare to look
							 // for the highest value in the left subtree
	while (max->R !=NULL) //if the node to the right of max isn't equal to null, do the following
		max=max->R;        //set max equal to the node to the right of it (highest value in left subtree)
	ptr->info=max->info;  //move the info from max into ptr
	deleteNode(ptr->L,max->info);
}
else
if (ptr->L==NULL)
{	
	printf("Entered inside ptr->L equal to null if statement \n");
	if (ptr->R==NULL)
	printf ("ptr->R equals NULL \n");
	TreeNodeT tempRight=ptr->R;
	if (tempRight==NULL)
	printf("tempRight equals NULL \n");
	printf ("ptr equals %s \n",ptr->info->name);
	ptr=ptr->R; 
	if (ptr==NULL)
	printf("ptr equals NULL \n");
	free(tempRight);
}
else
if (ptr->R==NULL)
{
	printf("Entered inside ptr->R equal to null if statement \n");
	TreeNodeT tempLeft=ptr->L;
	ptr=ptr->L; 
	free(tempLeft);

}
printf("Pre-exiting function check. \n");
if (ptr==NULL)
printf("PTR still equals NULL \n");
printf("Exiting Function \n");
return;
}

Note: There's still some print statements in there I was using for debugging (which I finally gave up on 5 hours later). I've tested findNode multiple times outside of the function and it IS correctly finding the nodes so that's not the issue.
Please help, anything to set me in the right direction would be amazing.
Anthony Vitello

You almost certainly don't want to call deleteNode recursively. You may want to call free, to get rid of the max node that you moved up in the tree, but that's it.

I'm not quite sure I understand why you shouldn't be using recursion on this as well as what I -should- be freeing.

As it stands i'm always using the same "Tree" input for testing. I input the following characters into the tree in this order "k,d,b,a,c,g,h,s".

If I try to remove the A (which is a leaf in this tree) all of my debugging print statements show me that the node gets set to null but when I print the tree the A shows up nice and pretty.

If I try to remove the D it correctly sets the C over the D (putting the rightmost node of the leftmost tree in place of D) and than it recursively calls the function to delete the C starting from the node to the left of the one I was originally trying to delete (basically making that rightmost node a leaf and deleting it through the recursion). Unfortunately, when I print this tree, as well, the D is gone and replaced with a C but the other C is still in the tree.

And, for one more weird situation, if I try to delete the G all the occurs is my cygwin client printing <null> over and over again for a few seconds before returning me to the cygwin prompt.

Ugh i'm so lost!

You don't want to call the function recursively because the function is "deleteNode" not "deleteNodeAndABunchOfOtherNodesAtRandom".

When you try to delete D, it puts the C in where the D was. You NOW NO LONGER WANT TO DELETE ANYTHING, because you've already done what you were supposed to do. Use free to get rid of the extra memory where the C was (with "free(max)") and you're golden.

Thanks a bunch!