Deleted binary tree has an incorrect subsequent traversal

Question

I have an issue and it is really annoying me right now. I want to make a binary tree, delete it and then create a new one. I have been trying to make the program myself but I keep getting stuck on the issue: After deleting the binary tree using post-order traversal I try to make a new binary tree. But the initial tree has not been deleted, so in practice I am adding to the tree instead of making a new one.

I thought that I was doing something horribly wrong so I found some C code online, which executes the same core functionality as my code, source (Binary Tree in C code):

#include<stdlib.h>
#include<stdio.h>

struct bin_tree {
int data;
struct bin_tree * right, * left;
};
typedef struct bin_tree node;

void insert(node ** tree, int val)
{
    node *temp = NULL;
    if(!(*tree))
    {
        temp = (node *)malloc(sizeof(node));
        temp->left = temp->right = NULL;
        temp->data = val;
        *tree = temp;
        return;
    }

    if(val < (*tree)->data)
    {
        insert(&(*tree)->left, val);
    }
    else if(val > (*tree)->data)
    {
        insert(&(*tree)->right, val);
    }

}

void print_preorder(node * tree)
{
    if (tree)
    {
        printf("%d\n",tree->data);
        print_preorder(tree->left);
        print_preorder(tree->right);
    }

}

void print_inorder(node * tree)
{
    if (tree)
    {
        print_inorder(tree->left);
        printf("%d\n",tree->data);
        print_inorder(tree->right);
    }
}

void print_postorder(node * tree)
{
    if (tree)
    {
        print_postorder(tree->left);
        print_postorder(tree->right);
        printf("%d\n",tree->data);
    }
}

void deltree(node * tree)
{
    if (tree)
    {
        deltree(tree->left);
        deltree(tree->right);
        free(tree);
    }
}

node* search(node ** tree, int val)
{
    if(!(*tree))
    {
        return NULL;
    }

    if(val < (*tree)->data)
    {
        search(&((*tree)->left), val);
    }
    else if(val > (*tree)->data)
    {
        search(&((*tree)->right), val);
    }
    else if(val == (*tree)->data)
    {
        return *tree;
    }
}

void main()
{
    node *root;
    node *tmp;

    root = NULL;
    /* Inserting nodes into tree */
    insert(&root, 9);
    insert(&root, 4);
    insert(&root, 15);
    insert(&root, 6);
    insert(&root, 12);
    insert(&root, 17);
    insert(&root, 2);

    /* Printing nodes of tree */
    printf("Pre Order Display\n");
    print_preorder(root);

    printf("In Order Display\n");
    print_inorder(root);

    printf("Post Order Display\n");
    print_postorder(root);

    /* Search node into tree */
    tmp = search(&root, 4);
    if (tmp)
    {
        printf("Searched node=%d\n", tmp->data);
    }
    else
    {
        printf("Data Not found in tree.\n");
    }

    /* Deleting all nodes of tree */
    deltree(root);
    printf("Tree has been deleted\n");

    insert(&root, 90);
    insert(&root, 40);
    insert(&root, 150);
    insert(&root, 60);
    insert(&root, 120);
    insert(&root, 170);
    insert(&root, 20);

    print_inorder(root);
}

But the weird thing is, that the code I have found online has the same issue as mine. In the code above, in the main() function the tree is being deleted, and then new nodes are added to the tree. But once the nodes are added and the tree is printed inorder, it can be seen that the output is a combination of the two trees and not the second tree on its own.

In other words, this code has the exact same issue as mine. How can the issue for the above code be fixed? For reference, I am using CodeBlocks as my compiler and the output of the program with the issue I describe can be found here:

Note: I have included a code off the internet since I want to try and solve the exact described issue without sharing too much of my personal code.

Answer 1

As said in the comments, this is probably due to not setting the pointer to the deleted tree to null.

The following is a modified version of deltree that sets the pointer to the deleted tree to null.

void deltree(node** tree) // pass by reference 
{
    if (*tree)
    {
        deltree(&(*tree)->left);
        deltree(&(*tree)->right);
        free(*tree);
    }
    *tree = NULL; // set the pointer to the deleted tree to null
}

Note that in order for the deltree argument to be modified within the deltree function you will have to pass a pointer to that pointer, for example deltree(root); should now be deltree(&root);. This is known as pass by pointer.