Binary Search Tree remove() function

[xarrtarrant]

Im working on a BST remove function. I think I'm on the right track but I'm not sure. From what I understand there are 3 possible cases. A Node with no children, one child, or 2 children(this being the most complex). Can anyone tell me if im on the right track? Thanks for the help.

void BST::remove(int x)
{
	TreeNode *n;
	TreeNode *v;
	n= root;
	while(n != NULL && n->key != x){
		if(n->key > x){
			v = n;
			n = n->left;
		}
		if(n->key < x){
			v = n;
			n = n->right;
		}
	}
	if(n->key == x){
		if(n->right == NULL && n->left == NULL){
			v->right = NULL;
			v->left = NULL;
		}
		if(n->right != NULL && n->left == NULL){
			v->right = n->right;
		}
		if(n->right == NULL && n->left != NULL){
			v->left = n->left;
		}
		if(n->right != NULL && n->left != NULL){
			 TreeNode *temp = n->right;
                        TreeNode *othertemp;
			while(temp->left != NULL){
			othertemp = temp;
                        temp = temp->left;
			}
			n->key = temp->key;
            othertemp->left = NULL;
		}
	}
}

[a null byte]

Hmm, Looks like you didn't consider the case where x (which I believe is the key) doesn't exist in the tree.

[xarrtarrant]

Thanks for the reply. I assumed that line 16 would take care of that. It would only go into those cases if x did exist.

[arimeh]

You are on the right track. As algorithm help, take a look at:

http://www.cs.princeton.edu/~rs/AlgsDS07/08BinarySearchTrees.pdf

[Smac89]

You are not freeing memory as you should, removing link to a node does not mean it is "removed" from memory and this is what you should be doing