0

So I am writing a BST node removal function, but I cannot figure out a problem:

I have this node-data structure:

struct webentry
{
        char * topic;
        char * keyword;
        char * url;
        char * summary;
        char * review;
        int rating;
};

The problem occurs at the point where the node has a two children and its right child has a left child (meaning I need to find the inorder successor and replace it with):

else if ((root->right  != NULL) && (root->left !=NULL) && (root->right->left !=NULL))
        {
               node*tempr = root->right;
               node*templ = root->left;

                delete root->data.topic;
                delete root->data.keyword;
                delete root->data.url;
                delete root->data.summary;
                delete root->data.review;

                delete root;
                root = findis(tempr);
                root->right = tempr;
                root->left = templ;
                return 1;
        }

I wrote a findis function to deal with the inorder successor situation:

node* program4::findis(node* &root)
{       
        /*   cout to figure out what's going on
        cout<<"Topic: "<<root->data.topic<<endl; Finds it here
        cout<<"Keyword: "<<root->data.keyword<<endl; Finds it here
        */

        if ((root->left==NULL) && (root->right ==NULL))
        {
                node*temp = root;
                delete root;
                root = NULL;
                 /*
                cout<<"Topic: "<<temp->data.topic<<endl; Empty
                cout<<"Keyword: "<<temp->data.keyword<<endl; Finds
                */
                return temp;
        }
        else if ((root->left == NULL) && (root->right != NULL))
        {
                node*temp= root;
                node*tempn = root->right;
                delete root;
                root = tempn;

                 /*    
                cout<<"Topic: "<<root->data.topic<<endl;
                cout<<"Keyword: "<<root->data.keyword<<endl;
                */ 
                return temp;
        }
        else
        {
                return findis(root->left);
        }

The problem is: When the node inorder successor returns, topic part becomes NULL, everything else stays the same. I have used GDB to figure out where it deletes the contents of topic, and it is right where I marked, right after the if condition meets and deletes the root in the findis function. It doesn't delete any other data of the the node, I don't know why it even deletes it. Can anyone see what is happening here?

Luc Aux
  • 149
  • 10
  • 1
    A [side note](https://stackoverflow.com/questions/46991224/are-there-any-valid-use-cases-to-use-new-and-delete-raw-pointers-or-c-style-arr). – user0042 Nov 26 '17 at 08:55
  • Replace the `char *` with `std::string` in the `webentry` struct. Do this to see if there is anything really wrong with your BST, and not something wrong with erroneous handling of string data. – PaulMcKenzie Nov 26 '17 at 08:58
  • @PaulMcKenzie Unfortunately I am not allowed to use strings in this class :( I can't wait to be out for this reason. – Luc Aux Nov 26 '17 at 08:59
  • @LucAux -- Read my comment again. I stated to check if the issue is with `char *` or your BST by replacing `char *`, even on a temporary basis. – PaulMcKenzie Nov 26 '17 at 08:59
  • @PaulMcKenzie Well instead of a shallow copy, I deep copied the node member by member and it all works now. But I am a little confused as to why it behaved the way it behaved. – Luc Aux Nov 26 '17 at 10:46
  • @LucAux -- You should have provided a [mcve]. You were more than likely mismanaging memory. – PaulMcKenzie Nov 26 '17 at 15:20

0 Answers0