Simple Binary Tree Delete with 2 Child Problem

[deepecstasy]

So Im creating Simple Binary Tree, not BST. Im having problem in deletewith 2 child.
Method for deletion is DELETE WITH COPYING.

After deleteing, when I traverse the tree, it shows run time error,
Unhandled exception at 0x008B5853 in binarytree.exe: 0xC0000005: Access violation reading location 0xFEEEFEEE.

Here is the function:

void BinaryTree<mytype>::deletewithTwoChild(BTNode<mytype> *temp) //temp is the node which is to be deleted.
    {
        BTNode<mytype> *father = findfather(temp, root); //found address of father of temp node & stored it in pointer
        BTNode<mytype> *leaf = temp; //created a copy of temp node


    /////CASE 1 (for predecessor)
    if(temp==root || father->left==temp)    //if father is left child of its own father then
    {
        leaf = leaf->left;  //move leaf 1 time left
        while(leaf->right!=0 && leaf->left!=0)  //until leaf reaches the last node of tree which has no child
        {
            leaf = leaf->right; //move leaf 1 time to right
        }
        mytype var = leaf->key_value;   //created a template variable to store leaf's key
        leaf->key_value = temp->key_value;  //assigning temp's key to leaf
        temp->key_value = var;  //assigning leaf's key to temp
        deleteWithNoChild(leaf);    //finally delete the last node (which is the given node for deletion) after swap 
    }
    /////CASE 2 (for successor)
    else if(father->right==temp)    //if father is right child of its own father
    {
        leaf = leaf->right; //move leaf 1 time right
        while(leaf->right!=0 && leaf->left!=0)  //until leaf reaches the last node of tree which has no child
        {
            leaf = leaf->left;  //move leaf 1 time to right
        }
        mytype var = leaf->key_value;   //created a template variable to store leaf's key
        leaf->key_value = temp->key_value;  //assigning temp's key to leaf
        temp->key_value = var;  //assigning leaf's key to temp
        deleteWithNoChild(leaf);    //finally delete the last node (which is the given node for deletion) after swap
    }
}

Data Set I m using:

                   30
                  /  \
                 20  80
                /   /  \
              10  40    120
                   \     / \ 
                  60  100 140
                  / \     /  \
                50  70   130 150

Im trying to delete node 80, 60, 120, 140 when the run time error pops up. Plz help :((

[deceptikon]

0xFEEEFEEE is used to mark freed memory in Visual C++. You're using a dangling pointer after deleting it.

[deepecstasy]

I have dry run-ed this thing again & again, there is nothing out of bounds in memory that Im trying to acces, I have fixed every loose end, but still :(

[mrnutty]

leaf = leaf->left; //move leaf 1 time to right

That comment conflicts with that is written.

leaf->key_value = temp->key_value; //assigning temp's key to leaf

That's not really needed since leaf is going to be deleted right.

Also I'm not sure why you are treating left-child different than right child when deleting using that algorithm. All you are doing is swapping a leaf node with the node to be deleted and deleting the stale leaf node. I don't see how this algorithm has any relation to a leaf having two children as your function deleteWithTwoChild suggests. Just being nitpicky there. If this is fro homework, then you probably want to follow the proper guidlines.

Anyways, can you print out the tree after each deletion? Also what happens if father is null? Have sanity check to see if father or temp is null. If possible post full code in pastebin.com because, the problem might be elsewhere. Can you post your deleteWithNoChild function? And also the destructor for this class.

[deepecstasy]

If added mechanism for root, & if root is null, then deletewithTwoChild is called, I have applied error check in main func, & as far as father, father can't be null, its being searched fine.

Updated Func (still not working) :

void BinaryTree<mytype>::deletewithTwoChild(BTNode<mytype> *temp)
{
    BTNode<mytype> *father = findfather(temp, root); //found address of father of temp node & stored it in pointer
    BTNode<mytype> *leaf = temp; //created a copy of temp node

    /////CASE 1 (for predecessor)
    if(temp==root || father->left==temp)    //if father is left child of its own father then
    {
        leaf = leaf->left;  //move leaf 1 time left
        while(leaf->right!=0 /*&& leaf->left!=0*/)  //until leaf reaches the right most node of left subtree
        {
            leaf = leaf->right; //move leaf 1 time to right
        }
        mytype var = leaf->key_value;   //created a template variable to store leaf's key
        //leaf->key_value = temp->key_value;    //assigning temp's key to leaf
        temp->key_value = var;  //assigning leaf's key to temp
        if(leaf->right!=0)
        {
            deletewithOneChild(leaf);
        }
        else if(leaf->left==0 && leaf->right==0)
        {
            deleteWithNoChild(leaf);    //finally delete the last node (which is the given node for deletion) after swap 
        }
    }
    /////CASE 2 (for successor)
    else if(father->right==temp)    //if father is right child of its own father
    {
        leaf = leaf->right; //move leaf 1 time right
        while(/*leaf->right!=0 &&/* leaf->left!=0)  //until leaf reaches the left most node of right subtree
        {
            leaf = leaf->left;  //move leaf 1 time to left
        }
        mytype var = leaf->key_value;   //created a template variable to store leaf's key
        //leaf->key_value = temp->key_value;    //assigning temp's key to leaf
        temp->key_value = var;  //assigning leaf's key to temp
        if(leaf->left!=0)
        {
            deletewithOneChild(leaf);
        }
        else if(leaf->left==0 && leaf->right==0)
        {
            deleteWithNoChild(leaf);    //finally delete the last node (which is the given node for deletion) after swap 
        } //after swap
    }
}

deletewithNoChild function::

void BinaryTree<mytype>::deleteWithNoChild(BTNode<mytype> *temp)
{
    if(temp==root)  //if node is root node, then
    {
        delete root;    //delete root
        root = NULL;    //nullify root
    }
    else    //if its some other node
    {
        BTNode<mytype> *father = findfather(temp, root); //created father pointer to store address of father node of child 'temp' present in argument list
        if (father->left==temp) //if left pointer of father points to child node (to be deleted)
        {
            delete temp;    //then delete node
            father->left = NULL;    //Nullify left pointer
        }
        else if (father->right==temp)   //if left pointer of father points to child node (to be deleted)
        {
            delete temp;            //then delete node
            father->right = NULL;   //Nullify right pointer
        }
    }
}

Destructor::

BinaryTree<mytype>::~BinaryTree()    //Destructor
{
    cleartree(root);    //calling public cleartree function to destroy tree
}
//----------
void BinaryTree<mytype>::cleartree(BTNode<mytype> *leaf)  //private  function definition
{
    if (leaf != NULL)   //if tree is not empty
    {
        cleartree(leaf->left);  //recursive call with tree's left sub-tree address
        cleartree(leaf->right); //recursive call with tree's right sub-tree address
        delete leaf;    //delete node itself
    }
}

[mrnutty]

Simplify your delete to this

 void BinaryTree<mytype>::deleteWithNoChild(BTNode<mytype> *temp){
    delete temp;
    temp = NULL;
 }

No need to worry about finding its father and whatnot. That finding father in that function is probably causing the weird result, because in your deletewithTwoChild function, you don't swap the nodes, but just swap the values. So when you do findFather(temp) in your deleteWithNoChild, its not finding the father you want. Try that and see what happens.

[mrnutty]

Also, if you really need to findFather, since it looks like it is being used extensively, consider adding another pointer in your Node. That new pointer would just point to its parent if any.

[deepecstasy]

But if I do as you say, then a temp node is deleted, I don't know it was left child or right child of its father, so father's left or right will be pointing to something that doesn't exist, & error will pop up! So....

& here is findfather:

BTNode<mytype>* BinaryTree<mytype>::findfather(BTNode<mytype> *temp, BTNode<mytype> *leaf)
{
    BTNode<mytype> *father = 0;      //created a node pointer to store address of father 
    if (leaf!=0)    //if leaf node is not null, then search
    {
        if(leaf->left==temp || leaf->right==temp)   //if leaf node is father of temp, then
        {
            father = leaf;      //assign temp to father
        }
        if(father==0)   //if not found then, in tree
        {
            father = findfather(temp, leaf->left);  //search towards left child
        }
        if(father==0)   //if not found then, in tree
        {
            father = findfather(temp, leaf->right);//search towards right child
        }
    }
    return father;  //return address of father node, it may be 0 if node not found
}

[mrnutty]

If you are going that route, then in your deletewithTwoChild instead of swapping values, swap the actual node pointers.