jahirul islam jahirul islam - 3 months ago 12
C++ Question

How to delete all the nodes of BST for reuse in c++

I couldn't delete all the nodes of BST for reuse.For the first set of inputs my code works properly but fails later input.
I googled a lot and couldn't find any solution related my problem.
For clarification I am pasting my full source code.
I found this kind of question previously asked here
How to delete all nodes of a Binary Search Tree
I don't know python very much.
For this a asked here again about this topic.

#include<bits/stdc++.h>
using namespace std;
int size,c=0;
struct BstNode {
int data;
BstNode* left;
BstNode* right;
};

BstNode* insert(BstNode* root,int data) {
if(root==NULL) {
root=new BstNode();
root->data=data;
root->left=root->right=NULL;
}
else if(data<root->data) {
root->left=insert(root->left,data);
}
else {
root->right=insert(root->right,data);
}
return root;
}

void preorderTraversal(BstNode* root) {
if(root!=NULL) {

c++;
if(c==size) cout<<root->data<<endl;
else cout<<root->data<<" ";
preorderTraversal(root->left);
preorderTraversal(root->right);
}
}

void inorderTraversal(BstNode* root) {
if(root!=NULL) {
inorderTraversal(root->left);
c++;
if(c==size) cout<<root->data<<endl;
else cout<<root->data<<" ";
inorderTraversal(root->right);
}
}

void postorderTraversal(BstNode* root) {
if(root!=NULL) {
postorderTraversal(root->left);
postorderTraversal(root->right);
c++;
if(c==size) cout<<root->data<<endl;
else cout<<root->data<<" ";
}
}

void deletepostorderTraversal(BstNode* root) {
if(root!=NULL) {
deletepostorderTraversal(root->left);
deletepostorderTraversal(root->right);
delete root;
}
}

int main() {
int test_case;
while(cin>>test_case) {
cin>>size;
BstNode* root=NULL; //create the root
for(int i=0;i<size;i++) {
int data;cin>>data;
root=insert(root,data);
}
c=0;
cout<<"Pre.: ";
preorderTraversal(root);
cout<<"In..: ";
c=0;
inorderTraversal(root);
cout<<"Post: ";
c=0;
postorderTraversal(root);
cout<<endl;
deletepostorderTraversal(root); //delete all the nodes
//i can't reuse this code again.
// root=NULL;
// if(root==NULL) cout<<"Deleted"<<endl;
}
}

Answer

Pass root by reference, and set it to NULL after deletion is done:

void deletepostorderTraversal(BstNode*& root) {
                                   // ^
  if(root!=NULL) {
    deletepostorderTraversal(root->left);
    deletepostorderTraversal(root->right);
    delete root;
    root = NULL; // <<<<<<<<<<<<<<<<
  }
}

In your version the pointer will be passed by value, and changes made to it inside the function will never appear outside of the functions scope.

Using the signature as shown above, and setting root to NULL inside the function you can (re-)use insert() again with a root node set to NULL after calling deletepostorderTraversal().

See Live Demo