2

I made a Binary Search Tree (node) class:

class BstNode {
public:
    BstNode(int value);
    ~BstNode();
    BstNode* Delete(int value);

    // more methods

private:
    int value_;
    BstNode* left_;
    BstNode* right_;
};

With a destructor that looks like this:

BstNode::~BstNode() {
    delete left_;
    delete right_;
}

And a Delete function:

BstNode* BstNode::Delete(int value) {
    // If the value to be deleted is smaller than the root's key,
    // then it lies in the left subtree.
    if (value < value_) {
        if (left_ == nullptr) return nullptr;
        else left_ = left_->Delete(value);
    }

    // If the value to be deleted is larger than the root's key,
    // then it lies in the right subtree.
    else if (value > value_) {
        if (right_ == nullptr) return nullptr;
        else right_ = right_->Delete(value);
    }

    // If the key to be deleted is the same as root's key, then *this*
    // is the node to be deleted.
    else {
        // If this node has no children, then we can just delete it.
        if (left_ == nullptr && right_ == nullptr) {
            delete this;
            return nullptr;
        }

        // If this node has one child, then we can just set this node to
        // that child and delete this node afterwards.
        else if (left_ == nullptr) {
            BstNode* temp = right_;
            delete this;
            return temp;
        }
        else if (right_ == nullptr) {
            BstNode* temp = left_;
            delete this;
            return temp;
        }

        // If this node has two children, then we have to get the "in-order successor"
        // (the smallest node in the right subtree).
        else {
            BstNode *temp = right_->Smallest();

            // Copy that node's value to this node
            value_ = temp->value_;

            // Then delete that value from the right subtree
            right_ = right_->Delete(value_);
        }
    }
    return this;
}

What I'm confused about is this snippet:

else if (left_ == nullptr) {
    BstNode* temp = right_;
    delete this;
    return temp;
}
else if (right_ == nullptr) {
    BstNode* temp = left_;
    delete this;
    return temp;
}

If the call to delete calls the class's destructor, wouldn't I end up deleting the entire sub-tree (right or left)? However, when testing, it looks like the tree is doing exactly the thing I want it to do: delete a node, and "move up" the child sub-tree to where "this" is - with the sub-trees still intact.

Doing BstNode* temp = this;, to my knowledge, would just copy the pointers to left_ and right_, then the delete this call should destroy the data behind them.

Am I missing something about delete this?

6
  • As an aside, I think the safer thing to do would be to set this->left_ and this->right_ to nullptr before deleting this - would this be the way to fix it? Commented Sep 10, 2018 at 4:12
  • Basic question -- why does BstNode even have a destructor that destroys the left and right tree? What if you want to remove just that one node? It's just simpler to do this the "classical" way, where you traverse to the node you want to delete, isolate that one node, go through the algorithm to splice the existing branch onto where the node to delete would go, and just delete the node you isolated previously. Then you don't have to worry about trying to avoid the "cascading delete" calls. Commented Sep 10, 2018 at 4:29
  • The cascading delete is to prevent memory leaks - if you made a BstNode in a function, you would leak memory at the end of that function unless you deleted every child node recursively somehow. Commented Sep 10, 2018 at 4:43
  • The cascading delete is to prevent memory leaks -- That still doesn't address the issue I pointed out -- what if you want to delete just that one node? You would have to null out both the left and the right before you delete the node, so that your destructor doesn't gum up the works. Commented Sep 10, 2018 at 4:44
  • Yeah, the BstNode::Delete function is meant to delete just one node instead of the entire subtree -- which is why I was a little confused when I tried my code and it worked. Like @1201ProgramAlarm said, it turns out that you'd get dangling pointers -- which is "fine" (not really), until you re-use that memory location later (I think?). I think I like the method of setting left_ and right_ to nullptr first before deleting this, just because that way I keep preventing memory leaks. Commented Sep 10, 2018 at 5:00

2 Answers 2

3

BstNode* temp=left_ and BstNode* temp=right_ would store the value of left_ or right_ in a temporary variable. You're using delete this; after you store that value in temp. Now, after you use delete this;, left_ and right_ would be deleted but temp would still remain intact. delete this; would not have an effect on the value of temp (which has your left/right sub-tree) and you may now return the corresponding left/right subtree after the corresponding right/left subtree gets deleted (In this case either left_ or right_ point to NULL). I hope this helps! Also, using delete on a pointer to an object not allocated with new gives unpredictable results so be careful with that!

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

2 Comments

Oops, yeah, good point! I'd have to make sure to always do new BstNode() in code that uses this. This was just me brushing up on some C++, but in reality I'd probably make a wrapper class to hide BstNodes from users. Thanks!
I think the copies of the pointers don't help you though, since you're destroying the entire sub-trees. You'd get dangling pointers, like @1201ProgramAlarm said.
2

Since your BstNode destructor deletes both the left_ and right_ nodes, you encounter Undefined Behavior as a result of this sequence:

BstNode* temp = right_;
delete this;
return temp;

After the delete this statement, temp will become a dangling pointer since the object it points to has been deleted. You return that pointer, and store it back into another node, and eventually when you dereference that node anything can happen - including the program appearing to work properly.

You should either set right_ to nullptr before calling the delete, or change the destructor (and overall destruction sequence) to not delete the child nodes.

1 Comment

Ahh, ok. So I'm correct in thinking this is dangerous -- I just assumed that C++ would change the values (to zero or something?), but after thinking about it for a while I guess that would be unnecessary work. I'm going to go with setting right_ (or left_) to nullptr before deleting this, then. Thanks!

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.