Having difficulty with removing a node from my binary search tree

Question

I am creating a binary search tree that needs to be able to delete a node and return true if the node was properly deleted, or false if the value doesn't exist in the tree. I am doing this because I need to delete more than one number and I want to create a while loop to delete all of it while it is true. For example one tree has the following ints: {79, 83, 147, 71, 95, 49, 15, 191}. Another tree has the following ints {26, 79, 144, 88, 147, 200, 90 }. My task is to find any elements that are in tree 1 that are in tree 2 and delete them from tree 1 (In this case 79 and 147). I am wanting to create a loop that runs through all the numbers in tree 2 and search and delete from tree one. Here is what I have so far for the remove node function(Assuming the trees are already built and filled):

Node.h:

template<class ItemType>
class Node {
public:
    ItemType data;
    Node * left;
    Node * right;

    //Constructors / Destructors
    Node ();
    Node ( ItemType inData );
    ~Node ();
};

//--------------------------------------------------------------//
//--                Constructor / Destructor                  --//
//--------------------------------------------------------------//
/** Standard Constructor */
template<class ItemType>
Node<ItemType>::Node () {
    left = right = NULL;
}

/** Overload Constructor */
template<class ItemType>
Node<ItemType>::Node ( ItemType inData ) {
    data = inData;
    left = right = NULL;
}

/** Standard Destructor */
template<class ItemType>
Node<ItemType>::~Node () {
    right = left = NULL;
}

From Source.cpp:

Tree2.postorder_print ();

int ridOf = 79;

if (Tree2.remove ( ridOf )) {
        Tree2.postorder_print ();
        cout << endl << "Number of Nodes: " << Tree2.get_num_of_nodes () << endl;
        cout << "Height:          " << Tree2.get_tree_height () << endl << endl;
    }

From Tree.h:

template<class ItemType>
void BTree<ItemType>::postorder_print_helper ( Node<ItemType> * inRoot, int & count ) {
    if (inRoot != NULL) {
        postorder_print_helper ( inRoot->left, count );
        postorder_print_helper ( inRoot->right, count );
        count++;
        std::cout << setw ( 4 ) << inRoot->data << " ";
        if (count % 5 == 0) { std::cout << endl; }
    }
} // end of void BTree<ItemType>::postorder_print_helper ( Node<ItemType> * inRoot )  




template<class ItemType>
void BTree<ItemType>::postorder_print_helper ( Node<ItemType> * inRoot, int & count ) {
    if (inRoot != NULL) {
        postorder_print_helper ( inRoot->left, count );
        postorder_print_helper ( inRoot->right, count );
        count++;
        std::cout << setw ( 4 ) << inRoot->data << " ";
        if (count % 5 == 0) { std::cout << endl; }
    }
} // end of void BTree<ItemType>::postorder_print_helper ( Node<ItemType> * inRoot ) 




template<class ItemType>
bool BTree<ItemType>::remove_helper (Node<ItemType> * inRoot, ItemType toRemove) {
    //if this is the node with the data
    if (inRoot->data == toRemove) {
        //Create Null Node that points to NUll
        Node<ItemType> * nullNode = new Node < ItemType > ;
        //if inRoot has No Children
        if (inRoot->left == NULL && inRoot->right == NULL ) {
            inRoot = nullNode;
            return true;
        }
        //if inRoot has 2 Children
        else if (inRoot->left != NULL && inRoot->right != NULL) {
            Node<ItemType> * temp = new Node < ItemType >;
            temp = return_max_value ( inRoot->left );
            Node<ItemType> * tempRight = new Node < ItemType >;
            tempRight = inRoot->right;
            Node<ItemType> * tempLeft = new Node < ItemType >;
            tempLeft = inRoot->left;
            inRoot = nullNode;
            inRoot = temp;
            temp->left = tempLeft;
            temp->right = tempRight;

            return true;
        }
        //if inRoot has 1 child
        else {
            //if inRoot has left child
            if (inRoot->right == NULL) {
                Node<ItemType> * temp = new Node < ItemType >;
                temp = inRoot->left;
                inRoot = nullNode;
                inRoot = temp;
                return true;
            }
            //if inRoot has right child
            else {
                Node<ItemType> * temp = new Node < ItemType >;
                temp = inRoot->right;
                inRoot = nullNode;
                inRoot = temp;
                return true;
            }
        }
    }
    //If not the node with the data See if toRemove is less than inRoot and perform recursive action
    else if ( toRemove < inRoot->data ) {
        remove_helper ( inRoot->left, toRemove );
    } //end if (toRemove < inRoot->data) 
    //See if toRemove is greater than inRoot and perform recursive action
    else if ( toRemove > inRoot->data)  {
        remove_helper ( inRoot->right, toRemove );
    }// end of else 

    //return false if data cannot be found
    else return false;
}

Some of my results are different and all wrong. One result is the infinite loop that keeps printing the tree over and over. Another result is it preforms the delete and appears to be successful but if you look at the two printouts, they are the same and the node was not deleted (if false was returned it shouldn't print it out again but it does). Then the third result happens during the second print_preorder. It breaks and it stops on a null node but the data, left and right all say "Unable to read memory." What did I do wrong? I can't figure it out. All of my other tree functions (to include the preorder print) until I try to delete a node.

Just to clarify a bit more, I am having issues with my remove_helper function. So I can move onto deleting the nodes that exist in Tree2 from Tree1.

Answer 1

OK with lots of help from @TheDark this is my remove_helper function:

template<class ItemType>
bool BTree<ItemType>::remove_helper (Node<ItemType> * &inRoot, ItemType toRemove) {
    //if this is the node with the data
    if (inRoot->data == toRemove) {
        //if inRoot has No Children
        if (inRoot->left == NULL && inRoot->right == NULL ) {
            inRoot = NULL;
            std::cout << "one" << std::endl;
            return true;
        }
        //if inRoot has 2 Children
        else if (inRoot->left != NULL && inRoot->right != NULL) {
            inRoot->data = return_max_value ( inRoot->left )->data;
            remove_helper (inRoot->left,inRoot->data);
            std::cout << "two" << std::endl;
            return true;
        }
        //if inRoot has 1 child
        else {
            std::cout << "zero" << std::endl;
            //if inRoot has left child
            if (inRoot->right == NULL) {
                Node<ItemType> * temp = new Node < ItemType >;
                temp = inRoot->left;
                inRoot = NULL;
                inRoot = temp;
                return true;
            }
            //if inRoot has right child
            else {
                Node<ItemType> * temp = new Node < ItemType >;
                temp = inRoot->right;
                inRoot = NULL;
                inRoot = temp;
                return true;
            }
        }
    }
    //If not the node with the data See if toRemove is less than inRoot and perform recursive action
    else if ( toRemove < inRoot->data ) {
        remove_helper ( inRoot->left, toRemove );
    } //end if (toRemove < inRoot->data) 
    //See if toRemove is greater than inRoot and perform recursive action
    else if ( toRemove > inRoot->data)  {
        remove_helper ( inRoot->right, toRemove );
    }// end of else 

    //return false if data cannot be found
    else return false;
}

After making the parameters as pass by reference, I fixed the deletion of a node with 2 children. I just copied the data from the max value on the left and then deleted the node that it came from recursively. Now that this is complete, I can move on to my next step! Thanks everyone.

Answer 2

remove_helper is attempting to change the value of the inRoot parameter. However inRoot is passed by value, so any changes made in your function are not reflected in the calling function.

Change the remove_helper function to take inRoot by reference, and then it will be able to modify the value of the parameter used in the calling function:

template<class ItemType>
bool BTree<ItemType>::remove_helper (Node<ItemType> * &inRoot, ItemType toRemove) {

Also this code doesn't seem right:

    //Create Null Node that points to NUll
    Node<ItemType> * nullNode = new Node < ItemType > ;

That node isn't pointing to NULL, it is pointing to an empty node. Further down in your code you are checking for inRoot->left == NULL, so you should be setting your pointers to NULL, not to point to an empty node.

You also have quite a few memory leaks, remember - if you create something with new there should be a corresponding delete somewhere as well.

Edit: One more thing - you never want to do this:

 Node<ItemType> * tempRight = new Node < ItemType >;
 tempRight = inRoot->right;

You are allocating some memory and pointing to it in tempRight, then immediately setting tempRight to something else. This is leaking memory and is unnecessary - you don't need to allocate memory for every pointer. Change it to:

 Node<ItemType> * tempRight = inRoot->right;

Answer 3

What you are trying to do is an inverted intersection between two trees. You could do this by creating a function with two arguments. One argument being the tree you want to remove stuff from (tree1) and the other being the tree you want to check (tree2).

In the function you then use recursion the check tree2. For each element you take out you use that element to search if it exist in tree1 (and in that case also remove it). Then you keep searching tree1 for every node in tree2 until you've gone through every element in tree2.