CODEWITHSUNDEEP
c++recursionbinary-search-tree
Derp
Derp

Reputation: 929

Binary Search Tree Recursive Remove

My program keeps breaking when I try to find the max of my remove function. What I'm trying to do is overwrite what the user wants to remove with the maximum of the left tree, then delete that node instead. It keeps breaking once it reaches the first Else. The recursion is breaking my mind. Where's my flaw?

This is the remove function with its private recursive sibling. 

template<typename TYPE>
bool BinarySearchTree<TYPE>::remove(TYPE& data)
{
    bool found = search(dataOut);
    if(found)
        TRoot = Premove(TRoot, data);
    return found;
}

template<typename TYPE>
Node<TYPE>* BinarySearchTree<TYPE>::Premove(Node<TYPE>* root, TYPE& data)
{
    Node<TYPE>* del;
    Node<TYPE>* max;
    if(root)
    {
        if(root->data > data)
            root->left = Premove(root->left, data);
        else if(root->data < data)
            root->right = Premove(root->right, data);
        else
        {
            if(root->left && root->right)
            {
                max = root->left;
                while(max->data < max->right->data)
                    max = max->right;
                root->data = max->data;
                max = Premove(root, max->data);

            }
            else
            {
                del = root;
                root = (root->right) ? root->right : root->left;
                delete pDel;
            }
        }
    }
    return root;
}

Upvotes: 0

Views: 3021

Answers (2)

Mehdi Darabi
Mehdi Darabi

Reputation: 1

I think your while statement should be like this:

while(max && max->right && max->data < max->right->data )

In some cases in your code, max or max->right could be NULL and it cause run_time error.

Upvotes: 0

nullptr
nullptr

Reputation: 11058

The problem is most probably here: while(max->data < max->right->data) max = max->right;

You are running out of the tree (max->right will become NULL eventually). Actually, as it's a binary search tree, there is no need to compare data. It's enough just to walk to the right while it's possible: while (max->right) max=max->right;

Also note the last assignment in this branch: there are two additional problems. First of all, instead of max = Premove(...) you should do root->left = Premove(...) (otherwise you will not modify the root->left reference). Second, you should call Premove for root->left and not for root: root->left = Premove(root->left, max->data); (otherwise you just get an infinite recursion).

Upvotes: 2

Related Questions