Delete function for binary tree at leaf level crashing

[drunkenmonk]

My delete function set works perfectly for all nodes but the leaves. The program doesn't crash until I try traversal again, not when actually deleting a node.
Here is my code:

void BinaryTree::DeleteNode(int deleteItem)
 {
	 TNode *current;
	 TNode *trailCurrent;
	 bool found = false;

	 if (root == NULL)
		 cout << "THE TREE IS EMPTY. THERE IS NOTHING TO DELETE." << endl;
	 else
	 {
		 current = root;
		 trailCurrent = root;

		 while (current != NULL && !found)
		 {
			 if (current->datum == deleteItem)
				 found = true;
			 else
			 {
				 trailCurrent = current;
				 if (current->datum > deleteItem)
					 current = current->leftPtr;
				 else
					 current = current->rightPtr;
			 }
		 }
		 if (current == NULL)
			 cout << "THE ITEM TO BE DELETED IS NOT IN THE TREE." << endl;
		 else if (found)
		 {
			 if (current == root)
				 DeleteFromTree(root);
			 else if (trailCurrent->datum > deleteItem)
				 DeleteFromTree(trailCurrent->leftPtr);
			 else
				 DeleteFromTree(trailCurrent->rightPtr);
		 }
		 else
			 cout << "THE ITEM TO BE DELETED IS NOT IN THE TREE." << endl;
	 }


void BinaryTree::DeleteFromTree(TNode* p)
{
	TNode *current;
	TNode *trailCurrent;
	TNode *temp;

	if (p == NULL)
		cout << "ERROR: THE NODE TO BE DELETED IS NULL." << endl;
	else if (p->leftPtr == NULL && p->rightPtr == NULL)
	{
		temp = p;
		p = NULL;
		delete temp;
	}
	else if (p->leftPtr == NULL)
	{
		temp = p;
		p = temp->rightPtr;
		delete temp;
	}
	else if (p->rightPtr == NULL)
	{
		temp = p;
		p = temp->leftPtr;
		delete temp;
	}
	else
	{
		current = p->leftPtr;
		trailCurrent = NULL;

		while (current->rightPtr != NULL)
		{
			trailCurrent = current;
			current = current->rightPtr;
		}

		p->datum = current->datum;

		if (trailCurrent == NULL)
			p->leftPtr = current->leftPtr;
		else
			trailCurrent->rightPtr = current->leftPtr;

		delete current;
	}

}//End DeleteFromTree
//===================

Any help is greatly appreciated!

[daviddoria]

I'd suggest building the smallest tree possible (a root and one leaf) and then stepping through with a debugger. Then you can see what is going on when you know exactly what SHOULD be going on.

Good luck,

Dave

[AkashL]

The leaf is deleted but how is the node with the pointer to the leaf updated and set to null? During traversal this pointer will be used even though it has been deleted?

[AkashL]

p = NULL;

is setting a copy of the address to NULL. When you go back to main the address will not be NULL it will be the same as before. The program below illustrates the problem.

#include<iostream>

void func(int *p)
{
	int *temp = p;
	p = NULL;
	delete temp;
};

int main()
{
	int* p = new int;

	func(p);

	std::cout << p << std::endl;
	return 0;
}