C++ delete node and its child nodes

Question

Please help me. I am stuck at this. What am I trying to do: Binary search tree. I am a C# developer and I learn C++ for about 2 weeks, therefore don't be so harsh with me and that's why pointers are still difficult for me.

I have a struct Node

struct Node
    {
        int Value;

        Node* _LeftNode;
        Node* _RightNode;

        Node(int value)
            : Value(value), _LeftNode(NULL), _RightNode(NULL)
        {
        }
    };

and a Delete() function in BinarySearchTree.cpp

void BinarySearchТрее::Delete(Node* node)
{
    if (node)
    {
        Delete(node->_LeftNode);
        Delete(node->_RightNode);
        delete(node);
        node = NULL;
    }
}

I want to delete the node and all of its child nodes. When I first step in the recursion... For example: Enter the recursion

I have two child nodes with values 10 and 19. With recursion, I delete the nodes and set the pointers to NULL. NULL node

And here is the problem: When I came out from the recursion the nodes are not NULL, but something strange. After recursion

And this is my problem. Why when I am in the recursion and I NULL the pointer everything is fine, but when I come out the pointer is something else.

[What are the rules about using an underscore in a C++ identifier?](https://stackoverflow.com/q/228783/10147399) — Aykhan Hagverdili, Feb 05 '21 at 09:57
I think you are confused with the concept of pointer. First of all `node = NULL;` does not do anything useful. Is that supposed to mean the parent node's left or right is set to null? — Hanjoung Lee, Feb 05 '21 at 10:00
Yes, exactly. I am trying to delete the memory and NULL the pointers but I keep getting some value after i came out from recursion — Gabby, Feb 05 '21 at 10:06
@Gabby With the microsoft compiler, when you delete something the memory gets filled with `0xdd` bytes. It's a debugging aid, not an error. Your code looks fine to me (apart from `node = NULL;` which is not wrong but unnecessary). — john, Feb 05 '21 at 10:14
@Gabby I think I see where your confusion is. You think that because you write `node = NULL` that when you step out of the recursion the left and right pointers should be NULL?, But `node` is a local variable, setting it to NULL has no effect on anything apart from that variable. It has no effect on the left and right pointers in the node you allocated because those are different pointers. — john, Feb 05 '21 at 10:19
@Gabby If (for some strange reason) you do want `Delete` to set the left and right pointers to NULL before you `delete` the node, then change your code to this `void BinarySearchТрее::Delete(Node*& node)`. The extra `&` makes `node` a reference, so now changes to it will effect the variable being refered to (i.e. the left and right pointers). — john, Feb 05 '21 at 10:22
@john thank you so much. It really helped me.I thought the pointer would work like ref in this case and its not a local variable. Thank you. — Gabby, Feb 05 '21 at 10:28
@Gabby It's a common error to think that pointers are somehow automatically references too. They aren't, they are values just like (for instance) integers. — john, Feb 05 '21 at 10:30
Thanks again. The tutorials from which I learn the language says that they are basically the same thing. Thank you. I will read more about them. — Gabby, Feb 05 '21 at 10:37
@john they still doing that? delete null pointer required to be no-op , that sounds like a broken tool — Swift - Friday Pie, Feb 05 '21 at 11:25
@Gabby The confusion is that, obviously, a pointer refers to whatever it is pointing at, but the pointer itself is also a value. So they have a dual nature, they refer to something else, but they are values as well. Most beginner confusion about pointers is a confusion about this dual nature. — john, Feb 05 '21 at 12:28

Hanjoung Lee · Answer 1 · 2021-02-05T10:48:44.543

0

As I talked in the comments, I think the thing is that how we can reset the pointer of the parent's(left or right child) of the initially passed node. (recursively deleting a node and its all children looks good.)

And I don't think it is possible in your current design. As Node does not contain a pointer to its parent, so there is no way to know who's the parent. node = NULL sets just the argument(local variable)'s value so it is pointless.

edited Feb 05 '21 at 10:48

answered Feb 05 '21 at 10:42

Hanjoung Lee

2,123
1
12
20

Yes I fixed it already. As a C# dev the concept of pointers and references is a little difficult for now. – Gabby Feb 05 '21 at 10:51
@Gabby but C# got those, in "unsafe" context, because some API need that – Swift - Friday Pie Feb 05 '21 at 11:29

score 0 · Answer 2 · answered Feb 05 '21 at 12:02

The C++ way would be to use std::unique_ptr.

struct Node
{
    int Value;

    std::unique_ptr<Node> LeftNode;
    std::unique_ptr<Node> RightNode;

    Node(int value)
        : Value(value)
    {
    }
};

Then to destroy a node and all of its children, you'd call reset on the appropriate std::unique_ptr<Node>

score 0 · Answer 3 · answered Feb 05 '21 at 12:04

I think what you actually want ist this:

struct Node
{
    int Value;

    Node* _LeftNode;
    Node* _RightNode;

    Node(int value)
        : Value(value), _LeftNode(NULL), _RightNode(NULL)
    {
    }

    ~Node() {
       delete _LeftNode;
       delete _RightNode;
    }
};

This way you are using the destructor to clean up recursivly. delete nullptr is ok btw.

EDIT:

the unique_ptr<> usage in one of the other answers is probably the smarter way to do this.

C++ delete node and its child nodes

3 Answers3