Is there any flaw in binary tree destructor algorithm-CodePudding

#include <bits/stdc  .h>
#define vi vector<int>

using namespace std;


class node{
    public:
        int data;
        node *left;
        node *right;

        node(){
            data = 0;
            left = right = nullptr;
        }

        node(int data){
            this->data = data;
            left = right = nullptr;
        }
};

class BT{
public:
    node *root{nullptr};
public:
    BT(){
        root = nullptr;
    }
    BT(const vi& v){
        // create a pair with initial state 0 and having root node in it
        stack<pair<node*,int> > st;
        root = new node(v[0]);
        pair<node*,int> p(root,0);
        st.push(p);

        int idx = 1;

        while(idx < v.size())
        {
            pair<node *,int> p = st.top();
            int state = p.second;
            int val = v[idx];

            if(state == 2)
            {
                st.pop();
                continue;
            }

            if(val == -1)
            {
                // will think for here
                // p.second  ;
                st.top().second  ;
                idx  ;
                continue;
            }

            // Now the value is not -1 and state is not 2

            node *newNode = new node(val);

            if(state == 0)
            {
                st.top().first->left = newNode;
                // p.first->left = newNode;
            }else{
                st.top().first->right = newNode;
                // p.first->right = newNode;
            }

            st.top().second  ;
            st.push(pair<node*,int>(newNode,0));
            idx  ;

        }
    }

    friend ostream& operator<<(ostream& os,BT& b){
        b.printHelper(b.root,os);
        return os;
    }

    void printHelper(node *root,ostream& os){
        if(root == nullptr)
            return;

        if(root->left != nullptr)
            os << (root->left)->data;
        os <<  " <- " << root->data << " -> ";

        if(root->right != nullptr)
            os << root->right->data;
        os << endl;
        printHelper(root->left,os);
        printHelper(root->right,os);
    }


    void levelOrderLineWise(){
        queue<node*> mq;
        queue<node*> hq;

        mq.push(root);

        while(!mq.empty())
        {
            node *removed = mq.front();

            cout << removed->data << " ";

            mq.pop();

            if(removed->left != nullptr)
                hq.push(removed->left);
            if(removed->right != nullptr)
                hq.push(removed->right);

            if(mq.empty())
            {
                cout << endl;
                mq.swap(hq);
            }
        }
    }


};

void destruct(node *root)
{
    if(root == nullptr)
    {
        return;
    }
    if(root->left != nullptr)
    {
        destruct(root->left);
        root->left = nullptr;
    }
    if(root->right != nullptr)
    {
        destruct(root->right);
        root->right = nullptr;
    }
    
    delete root;
}

int main(){
    #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
        freopen("error.txt","w",stderr);
    #endif
    /**
     *  Tree diagram
     *      50
     *     /  \
     *    25   75
     *   / \   / \ 
     *  12 37 62  87
     *      /  \
     *     30  70
     */
    vi v = {50,25,12,-1,-1,37,30,-1,-1,-1,75,62,-1,70,-1,-1,87,-1,-1};
    
    BT b(v);
//  b.levelOrderLineWise();
            
    destruct(b.root);
            
    if(b.root != nullptr)
    {
        cout << "root is still there" << endl;
    }else{
        cout << "tree destroyed" <<endl;
    }
    
    
    if(b.root->left != nullptr)
    {
        cout << "It is still there";
    }else{
        cout << "completed";
    }

    return 0;
}

INFO ABOUT CODE

This is the code for creating a binary tree,we have a class called node which has a data and two pointers to its children left & right.

The constructor takes a vector v and creates the tree using the elements of the vector in the preorder fashion.

Then I have a function levelOrderLineWise in the class BT which prints the tree in line wise fashion.

The function destruct is supposed to destroy the tree. The algorithm takes the root of the tree and destroys the left child(if it is not nullptr) and then makes left child of root equal to nullptr. Similarly, I have destroyed the right child(If it is present) and then made the right child of root equal to nullptr.

I get that this algorithm would not make the root of the tree nullptr but i expect it to make root->left and root->right equal to nullptr. But to my disappointment i am not getting the desired output.

Is there any flaw in my logic? If no,then why is it that i am getting the message It is still there?

Any help would be appreciated.

EDIT

Basically, I get what @john is saying, i should not have included the conditions if(root->left != nullptr) and if(root->right != nullptr).

so this would translate something like this

void destruct(node *root)
{
    if(root == nullptr)
        return;

    destruct(root->left);
    // root->left = nullptr;
    destruct(root->right);
    // root->right = nullptr;
    delete root;
}

But I still dont get why is there not a need for the conditions root->left = nullptr and root->right = nullptr

reason why i think so they are necessary

From what i know is that whenever you deallocate the memory pointed by a pointer you must also set that pointer to nullptr.

CodePudding user response：

After you delete the pointer, you're not allowed to access the memory that it points to (it's undefined behavior and will likely lead to crashes). So, accessing b.root->left is illegal. In practice, when you deleted the root, it likely changed the memory there as some of its bookkeeping for tracking memory allocations, which is probably why the data that's where b.root->left used to be is nonzero. It's good practice to set the pointer to nullptr whenever you delete it so you can't make this kind of mistake as easily.

CodePudding user response：

It could be a lot simpler

void destruct(node *root)
{
    if(root == nullptr)
        return;
    destruct(root->left);
    destruct(root->right);
    delete root;
}

does exactly the same as your code.

root->left and root->right cannot have any defined value after delete root; so I'm not sure what you are expecting.