Well here is what he says should be done to make this happen:

if Item not found

1. Do nothing

else

1. if node is a leaf

change to NULL

2. if node has one child

promote child

3. if node has two children

find largest in nodes left branch

recursively remove it.

use it as parent of the two subtrees

Ok, well this sounds reasonable and all that. The issue is that we are supposed to do this without a node argument in the function. That only leaves me with a "this" pointer to get a hold of this stuff...I can't change a "this" pointer. How can I promote the next node?

In case three I was told that I should find the largest node in the left subtree and call removeKey() on it and the tree would recursively build it's self.

Either way, here is my issue. If I try and remove the first node in the tree I always end up with an empty tree. If I try and remove any other node in the tree the recursion runs into infinity.

In all cases this function is supposed to return the removed node.

Here is the BST function:

/** * Removes the node corresponding to the given key. */ NodeData* removeKey(int key) { if (root == NULL) { return NULL; } else { BinaryTreeNode *removed = root->removeKey(key); if (removed == root) { root = removed->left; } removed->left = NULL; removed->right = NULL; NodeData *data = removed->data; delete removed; return data; } }

Here is my complete and utter fail:

/** * Removes the node that matches the given integer key from the Binary Tree * rooted at this Node. * * Returns the removed BinaryTreeNode, with its left child set to the new * root of this subtree. */ BinaryTreeNode* BinaryTreeNode::removeKey(int key) { if (this == NULL) { return NULL; } else if (key < data->key) { return left->removeKey(key); } else if (key > data->key) { return right->removeKey(key); } else { if (this->isLeaf()) { return this; } else if (this->getChildCount() == 1) { if (left == NULL) { right->removeKey(key); return this; } else { left->removeKey(key); return this; } } else { BinaryTreeNode *curr = left; while (curr->right != NULL) { curr = curr->right; } curr->removeKey(key); return this; } } }

This post has been edited by **SpeedisaVirus**: 12 October 2009 - 10:11 PM