Binary Tree with parent pointer in node keeps crashing on Deletion with error 0xDDDDDDDD

Question

I was experimenting a little bit with C++ and decided to try and create whole tree deletion method for Binary Tree. For some reason I keep getting pointer error because pointer is 0xDDDDDDDD.

If someone can explain me why it does not work I would appreciate it so I can learn more about pointers.

struct Node {
    Node*  parent;
    Node *left,
         *right;
    int value;


   inline Node() : parent(nullptr), left(nullptr), right(nullptr), value(0){}

   ~Node() = default;

};

class BST {
public:
    Node* root;

    
public:
    BST() = default;
    inline BST(int i)
    {
        root = new Node();
        root->value = i;
        root->parent = nullptr;
        root->left = nullptr;
        root->right = nullptr;
    }
    BST(const BST& bst) = default;
   

    void Insert(int i);
    void DeleteAll(Node* node);


};

#include <iostream>

int main()
{
    BST t(20);
    t.root->left = new Node();
    t.root->left->value = 22;
    t.root->left->parent = t.root;

    t.root->right = new Node();
    t.root->right->value = 15;
    t.root->right->parent = t.root;



  


    t.DeleteAll(t.root);
    
}


void BST::Insert(int i)
{
   

}



void BST::DeleteAll(Node* node)
{ 
 
    Node* target = node;

    std::cout << "Probing node with value " << node->value << std::endl;


    if (node->left == nullptr && node->right == nullptr)
    {
        target = node->parent;  
        std::cout << "Node deleted with value: " << node->value << std::endl;     
        delete node;    

        if (target == nullptr)
        {
            std::cout << "Found and deleted root!" << std::endl;
            return;
        }

        std::cout << "Parents node value: " << target->value << std::endl;     
    }

    else if (node->left != nullptr)
    {
        std::cout << "Found left ptr with value: " << node->left->value << std::endl;
        target = node->left;

    }
    else if(node->right != nullptr)
    {
        std::cout << "Found right ptr with value: " << node->right->value << std::endl;
        target = node->right; 
    }

    DeleteAll(target);

}

The prompt from the console I am getting is:

Probing node with value 20
Found left ptr with value: 22
Probing node with value 22
Node deleted with value: 22
Parents node value: 20
Probing node with value 20
Found left ptr with value: -572662307
Probing node with value -572662307

In DeleteAll() function when it gets back to parent node to search if there is any children that is not null it always finds the left child which I deleted before. Shouldn't it be null?

And there it crashes. I have no idea why is it doing that but something is probably in the delete function. This is not a homework of any kind I am just trying to learn why this does not work.

Answer 1

When I run your code I get this output, and it throws "read access violation":

Found left ptr with value: -572662307

-572662307 is same as 0xDDDDDDDD This is specific for Visual Studio in debug mode. Sometimes you may not get this value.

The problem is you never allocated memory for parent (which you don't even need, more on that later) then you try to delete it over and over.

You should rewrite you code like this to understand it better:

void DeleteAll(Node* node)
{
    printf("node: %p\n", node);
    Node* target = node;
    if (!node->left && !node->right)
    {
        target = node->parent; //this was never allocated, supposed to be NULL
        delete node; 
        if (target == nullptr) //target is now undefined, not NULL, can't be tested
            return; //we may not get here
    }
    else if (node->left != nullptr)
        target = node->left;
    else if (node->right != nullptr)
        target = node->right;

    DeleteAll(target); //could be deleting the same thing again
}

The output is something like this, with different numbers:

node: 012C5078
node: 012D2F00
node: 012C5078
node: 012D2F00
node: DDDDDDDD

You see the same values repeated, it's trying to delete twice. The correct DeleteAll function is just this:

void BST::DeleteAll(Node* node)
{
    if (!node)
        return;
    DeleteAll(node->left);
    DeleteAll(node->right);
    delete node;
}

You will also need a different Delete(Node* node, int value) function which deletes based on value,left,right, this will be used once you properly insert items, and you want to remove some values before BST is destroyed.

Try this example instead:

https://gist.github.com/harish-r/a7df7ce576dda35c9660