Removing A Node From A Binary Search Tree

Question

In the code below, I've tried to implement a basic remove operation. However before even getting started at the complex removal part, I've failed removing the leaf node . I guess it can be related where the variable is defined however I can't get to solve it. Any ideas would be appreciated.

The part where I wanted to delete the node is basically implemented as the delete temp; part (by the way if I insert it as delete[]temp; it still won't work).

void remove(int value){
        if(root==NULL)
            cout<<"The list is empty!"<<endl;
        else {
            Node *temp=root;
            while(temp!=NULL)
            {
                cout<<"Processing: "<<temp->data<<endl;
                if(value==temp->data)
                {
                    cout<<"Data verified"<<endl;
                    //DELETE ROOT
                    if(temp->left && temp->right) //If it has two children
                    {
                        cout<<"Root with two children"<<endl;
                        return;
                    }
                    if(temp->left || temp->right)
                    {
                        cout<<"Root with a single child"<<endl;
                        return;
                    }
                    else {
                        cout<<"Leaf node"<<endl;
                        delete temp;
                        return;
                    }
                }
                else if(value<temp->data){
                    if(temp->left)
                        temp=temp->left;
                    else
                        return;
                }
                else{
                    if(temp->right)
                        temp=temp->right;
                    else
                        return;
                }


            }
        }
    }

Answer 1

The delete operator doesn't do what you think it does. What it does is that marks the memory that was used by the object as unused, which means it can be used again (it also calls the destructor of the object, but that's not relevant here).

What it won't do is modifying any pointers that point to the deleted object, you have to do that yourself.

So, the correct code for that branch would have to access the parent of the deleted node, and set its left or right field (depending on which the deleted node is) to NULL. Only then you can actually delete the node.