How to remove Specific Node is Binary Search Tree?

Question

I am trying to delete the specific Node but I don't see where the problem is.

Actually, I get the Node through the Find() and then delete it with Remove().

The program crashes whenever Delete() fires.

bool RemoveNode(int key)
{
    if (IsEmpty())
        return false;
    Node* r = Find(key,root);
    if (r==nullptr)
        return false;
    return Remove(r);
}
bool Remove (Node* &r)
{
    if (r->left==nullptr && r->right ==nullptr)
    {
        delete r;
        r=nullptr;
        return true;
    }
    if (r->left==nullptr)
    {
        Node* temp = r->right;
        delete r;
        r=nullptr;
        r=temp;
        return true;
    }
    if (r->right==nullptr)
    {
        Node* temp = r->left;
        delete r;
        r=nullptr;
        r=temp;
        return true;
    }
    Node* Max = FindMax(r->left);
    r->data = Max->data;
    Remove(Max);

    return true;
}
Node* FindMax(Node* r)
{
    if(r->right==nullptr)
        return r;
    return FindMax(r->right);
}
Node* Find(int key, Node* &r)
{
    if (r==nullptr)
        return nullptr;

    if (r->data==key)
        return r;

    if (key < r->data)
        return Find(key,r->left);
    else
        return Find(key,r->right);
}

Don't you have to update the "parent" to no longer point to the deleted child node? — Justin
– Justin, Commented Oct 29, 2013 at 19:32

Artemis · Accepted Answer · 2017-08-10 05:23:26Z

1

Clearly, your Remove() function is intended to modify the pointer to the node, independent on where it is located: instead of passing in the raw pointer, you are passing in a reference to the pointer. This way, you could update the tree's root pointer, the left or right as a component of the next. As long as you pass it in the correct reference, I think the code should work.

The variable r is actually modified in Remove() which is a local variable defined in RemoveNode(): the result of Find() is a pointer, not a reference to the relevant pointer. However, you need to modify the pointer in your tree structure pointing to the node, not an arbitrary local variable.

The fix would be the use a special version of Find()' which correctly returns a reference to the pointer rather than the pointer itself. Your recursiveFind()would be up to the task if it returned aNode*&rather than aNode*`. Since your tree doesn't seem to be balanced and stack space is relatively limited, I'd rather use a non-recursive function. Instead of returning a reference to a pointer it would maintain a pointer to a pointer to the current node instead of a pointer to the node:

Node** InternFind(int key) {
    Node** n = &this->root;
    while (*n && (*n)->key != key) {
        n = &(key < (*n)->key? (*n)->left: (*n)->right);
    }
    return n;
}

The code is untested and probably not quite right. Once you got the pointer to the pinter, however, you can just update it without dealing with where the came from:

Node** r = InternFind(key);
if (*r) {
    Remove(*r);
    return true;
}
else {
    return false;
}

Although I don't know what "if Delete() fires" means, I'd assume you have a problem with duplicate uses of delete p for the same pointer p. The code probably goes wrong long before that accessing stale nodes.

edited Aug 10, 2017 at 5:23

Artemis

13913 bronze badges

answered Oct 29, 2013 at 20:30

Dietmar Kühl

155k18 gold badges238 silver badges395 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

j_random_hacker Over a year ago

r is actually Node* &r, so changing it correctly changes the passed-in parameter. Justin identified the real problem: child pointers not being updated in the parent after Remove() is called.

Dietmar Kühl Over a year ago

@j_random_hacker: Thanks for the downvote but given that r is defined as Node* r = Find(key,root); the fact that it is passed as a reference when using Remove(r); doesn't really help. Admittedly, the function where it is defined is RemoveNode() rather than Remove(), however (I edited the answer on a mobile phone which makes it hard to keep track of the exact details). The point is: if the correct reference were passed in (which you'd do, e.g., by locating the pointer to pointer to the node and then dereferencing it), you'd update the pointer in the parent!

j_random_hacker Over a year ago

I see what you mean. Another way (equivalent to your InternFind() I think) would be just changing the return type of Find() to Node*& -- a reference is as good as a pointer. (It looks like the OP might have been going for something like this, what with the otherwise inexplicable Node* &r parameter to Find()). If you clarify what's going on with the reference in your answer, I'll +1.

Dietmar Kühl Over a year ago

@j_random_hacker: I updated the description and added a comment on why I'd prefer a non-recursive version of Find() (and, yes, I realize that the function is tail-recursive but there is no requirement for C++ compilers to eliminate tail-recursion).

Collectives™ on Stack Overflow

How to remove Specific Node is Binary Search Tree?

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related