Program crashes while comparing pointers to NULL

Question

 template<class item_type>
 struct node{
     item_type x;
     node<item_type> *left;
     node<item_type> *right;
     //functions
 };

 template<class item_type, class param>
 class Tree{
        node<item_type> *root;
    public:
        item_type Get_Item(param item);
        void Add_Item(item_type item);
        void Delete_Item(item_type item);

        //more functions

        Tree();
};


template<class item_type, class param>
Tree<item_type, param>::Tree()
{
    this->root = new node<item_type>;

    this->root->left=NULL;
    this->root->right=NULL;

}   

ADD ITEM:

void Tree<item_type, param>::Add_Item(item_type item)
{

    node<item_type> newItem;
    newItem.x = item;
    node<item_type> *cur = root;
    node<item_type> *prev;

    if(cur->x==NULL)
        cur->x=item;

    int ifGreater;
    while(cur->left!=NULL || cur->right!=NULL)
    {
        if(item<cur->x)
        {
            ifGreater = 0;
            prev = cur;
            cur = cur->left;
        }
        else
        {
            ifGreater = 1;
            prev = cur;
            cur = cur->right;
        }
    }
    if(ifGreater==1)
        prev->right = &newItem;
    if(ifGreater==0)
        prev->left = &newItem;
}

Problem occurs here in this function at the cout<<1;

template<class item_type, class param>
    void Tree<item_type, param>::Delete_Item(item_type item)
    {
        node<item_type> *cur = root;
        node<item_type> *prev;

        int ifGreater;
        if(cur==NULL)
        {
            cout<<"Not found"<<endl;
            return;
        }

        while(cur!= NULL && (cur->left!=NULL || cur->right!=NULL))
        {   
            cout<<1; //crash occurs RIGHT before here as 1 is never printed
            if(item<cur->x)
            {
                //do something   
            }                              
        }

The problem occurs before the cout<<1 and after the declaration of int ifGreater; The cout is merely just to test where it runs and where it stops running. I run this function using a call to

int main()
{
     Tree<int,int> theTree;
     theTree.Add_Item(1); //so the tree isn't empty
     theTree.Delete_Item(1);
}

NOTE: The program doesn't even get past the first iteration, the improper handling of memory (which is fixed) was not the issue of this specific error.

Answer 1

You have undefined behavior in the following piece of code:

template <class item_type, class param>
void Tree<item_type, param>::Add_Item(item_type item)
{
    node<item_type> newItem;
    // ...
    if (ifGreater == 1)
        prev->right = &newItem;
    if (ifGreater == 0)
        prev->left = &newItem;       
}

Above, newItem is a local variable and you're keeping a pointer to that local well after it expires when Add_Item exits. This is likely the reason for the crash.

Additionally, you never initialized ifGreater or node<item_type> *prev;. Again, this results in more undefined behavior when this gets executed:

    if (ifGreater == 1)
        prev->right = &newItem;
    if (ifGreater == 0)
        prev->left = &newItem;       

You likely end up deferencing some random piece of memory. This is because there's no guarantee your while loop executes, eg. Consider the case where both left and right is NULL.