Thread: Recursive function

I am using this function to remove a node from a binary tree. It works fine in most situations. Often though it will leave either the left or right pointer from a parent null. So when I go to display it the program just blows up. Thanks for any ideas.

Code:

 
Node *Btree::remove(Node *root,int key)
{
	Node *index = NULL;
	Node *index2 = NULL;
	if(!root)
	   return root;
	if((root->getData())== key)
	{
		if(root->getLeft() == root->getRight())
		{
			delete root;
			return NULL;
		}
		else if(!root->getLeft())
		{
			index = root->getRight();
			delete root;
			return index;
		}
		else if(!root->getRight())
		{
			index = root->getLeft();
			delete root;
			return index;
		}
		else
		{
			index2 = root->getRight();
			index = root->getRight();
			while(index->getLeft())
			       index = index->getLeft();
			index->setLeft(root->getLeft());
			delete root;
			return index2;
		}
	}
	if(root->getData() < key)
	   root->setRight(remove(root->getRight(),key));
	else
           root->setLeft(remove(root->getLeft(),key));
	return root;
}

But is it safe to just delete a node without 'reconnecting' it's neighbors? (Set me straight if I'm being ignorant)

Anyhow, have you tried the tried and true printf dubug?

Yeah I know what you are saying and that's the problem. It does reset the pointers in most situations. In one particular set of test data I am using it doesn't work. I don't know I have looked at it for a while now. Is this a problem that is best solved some other way than recursion?

YES!!!! For those of you who may care (haha) I FINALLY!! got my function working beautifully. Although it looks completely different now (still recursive). Anyways, I'm happy.

I never have used binary trees. I don't want to learn em unless I have to either.

The binary tree is a structure that is completely dynamic. Not only that, but it basically sorts itself as it is constructed at run time. It is also quite easy to ensure that you don't add duplicate data to your structure. But man oh man was it hard for me to figure out how to remove certain nodes recursively without losing the whole structure. Now that I got it I got it. If that makes sense. So yeah, it's a nice structure. My professor told me that when I take a test to get a job in this language most of the questions will be on trees and linked lists so I would have to say it's pretty important.