c++ delete entire binary search tree

Question

for some reason my nodes don't seem to be deleting. it looks as though it traverses to the end ok but after the node is "deleted" it still has the data in it. i've also tried free(bNode) and bNode = NULL instead of delete bNode but they all give the same result.

The cout and display functions were just put in when I was trying to debug. I just don't understand why its not working, i hope i'm not missing something simple.

struct
Book{
char title [50];
char url [75];
Book *left;
Book *right;
};

void deleteAllBooks (Book *bNode){
    if(bNode==NULL) return;                                             
    if(bNode->left !=NULL){
        cout << endl << "deleting left" << endl;
        deleteAllBooks(bNode->left);
    }
    if(bNode->right !=NULL){
        cout << endl << "deleting right" << endl;
        deleteAllBooks(bNode->right);
    }
    cout << endl << "deleting node " << bNode->title << endl;
    delete bNode;
    displayBookTree(bNode);
}
void displayBookTree(Book *bNode){
    if(bNode==NULL){
        cout << "No books" << endl;
        return; 
    }
    if(bNode->left !=NULL){
        displayBookTree(bNode->left);
    }
    if(bNode->right !=NULL){
        displayBookTree(bNode->right);
    }
    cout <<"Title: " << bNode->title << endl;
    cout <<"URL: " << bNode->url <<endl;
}

For one thing delete doesn't set the pointer to NULL, and you only check for null. — dutt, Nov 21 '13 at 08:18
i tried using bNode = NULL but I still had the data... just ran it again like that and the data was removed from the pointer in the delete function but outside the function there is still data in the pointer that was passed into the delete function. hmm — Covertpyro, Nov 21 '13 at 08:23
The problem would go away by using `std::unique_ptr` inside `Book`. All this manual memory management makes code hard to read and frail. — MSalters, Nov 21 '13 at 08:36
The misunderstanding you have is that you think delete must remove your data. It doesn't have to. All it has to do is call the destructor and free the memory. You data might still be there, except now it's in free memmory so sooner or later it will probably get overwritten. — john, Nov 21 '13 at 08:52
i got it so the tree is emptied out in the deleteAllBooks function but if i call deleteAllBooks(Student->bookTree); the bookTree is not empty after the call even though it is inside the call. what am i missing? — Covertpyro, Nov 21 '13 at 09:16
You're fixated on this idea that delete must 'empty' your data, it's not true. Like I said all it does is free the memory. — john, Nov 21 '13 at 09:19
that doesn't make sense, if it's telling me it's null inside the function why would it no longer be null after the function? i don't think data can just disappear then come back. — Covertpyro, Nov 21 '13 at 09:24
Changes to variables inside a function don't change variables outside a function. That's a completely different issue. Clearly you're struggling with how pointers work in C++, and also I guess with the concept of undefined behaviour. — john, Nov 21 '13 at 09:26
If you assign to a pointer inside a function e.g. `p = NULL;` it has no effect at all on any other pointer variables (including those outside the function). If you delete a pointer, then it marks the memory pointed to as being free, but it does not (necessarily) modify the memory in any way. If you access memory that has been freed (which is what you are doing) then that is *undefined behaviour*. — john, Nov 21 '13 at 09:29
I thought I was changing data that the pointer is pointing to and that it would remain after the function was over. is that not correct? — Covertpyro, Nov 21 '13 at 09:31
No it's not correct. Neither `p = NULL;` or `delete p;` change what is being pointed to (except in the sense that delete marks the memory as free, and calls the destructor, but I don't think there is a destructor in your case). — john, Nov 21 '13 at 09:32

score 2 · Answer 1 · edited May 23 '17 at 11:50

"Use 0. The "NULL" macro is not type-safe; if you feel that you must use "null", make it a const int instead of the C-style "#define". Also see "The C++ Programming Language" for Stroustrup's argument against the usage of "NULL"."

I would try to change:

 if (bNode==NULL) { ... }

with

 if (!bNode) { ... }

And

if (bNode->left !=NULL) { ... }
if (bNode->right !=NULL) { ... }

with

if (bNode->left) { ... }
if (bNode->right) { ... }

And then take a look to this answer on how correctly delete a Struct!

score 0 · Answer 2 · answered Nov 21 '13 at 08:40

Easiest solution:

struct Book{
  std::string title;
  std::string url;
  std::unique_ptr<Book> left;
  std::unique_ptr<Book> right;
};

void deleteAllBooks (std::unique_ptr<Book> bNode)
{
  // No code necessary. Literally. But usually you wouldn't even 
  // bother with this function, the default Book::~Book is fine.
}

score 0 · Answer 3 · answered Nov 21 '13 at 09:02

Your solution is correct, but your observations are wrong. When you delete an object, the destructor will be executed for that object. In your case, this destructor has no visible side effect, because all your data members are plain old data types that do not have a destructor on there own. Using an object after it was deleted, invokes undefined behavior and your observation is one possible incarnation of "undefined behavior".

Your test for != 0 before calling deleteAllBooks() is redundant:

void deleteAllBooks ( Book *node ) 
{
    if( node ) 
    {
        deleteAllBooks( node->left );                                            
        deleteAllBooks( node->right );                                            
        delete node;
    }
}

does the same, but might be easier to understand.

And don't mix free/alloc with new/delete. If you've allocated an object with new, you have to return it with delete. Otherwise, you will get undefined behavior.

c++ delete entire binary search tree

3 Answers3