Whats wrong with the following delete node in binary tree functions?

[Nikhar]

Hi guys...I am learning binary trees and its quite interesting. But I am unable to make4 a the delete a node function in it. Whenever I try to delete a node, a fatal error occurs and the program closes.

Can you please point the error out for me in the following program?

The program's a bit on the lengthier side as it also contains the insert a node function and inorder traversal function but it should be easy to trace the delete function.

Thanks for the help in advance.

#include<iostream>
#include<cstdio>
#include<cstdlib>

using namespace std;

struct node
{
    int data;
    node *left;
    node *right;
};

class treetype
{
    node* root;
    public:
    treetype(){root=NULL;}
    bool finditem(const int &data);
    bool isempty();
    void insertitem(const int &data);
    void viewtree();
    void deletenode( int data);
};

bool find(node *,const int&);
void insert(node *&,const int&);
void view(node *tree);
void delete1(node *&,  int);
void delete2(node *&);
void getpredecessor(node *, int&);
bool treetype::isempty()
{
    if(root==NULL)
        return 1;
    else
        return 0;
}

bool treetype::finditem(const int &data)
{
    return find(root,data);
}

void treetype::insertitem(const int &data)
{
        insert(root,data);
}

void treetype::viewtree()
{
    view(root);
}

void treetype::deletenode(int data)
{
    delete1(root,data);
}

bool find(node *tree, const int &data)
{
    if(tree==NULL)
        return 0;
    else if(tree->data==data)
        return 1;
    else if(tree->data<data)
        return find(tree->right,data);
    else
        return find(tree->left,data);
}

void insert(node *&tree, const int &data)
{
    node *temp;
    temp= new node;
    temp->data=data;
    temp->right=temp->left=NULL;
    if(tree==NULL)
        tree=temp;
    else if(tree->data<data)
        insert(tree->right,data);
    else
        insert(tree->left,data);
}

void view(node *tree)
{
    if(tree!=NULL)
    {
        view(tree->left);
        cout<<endl<<tree->data;
        view(tree->right);
    }
}

void delete1(node *&tree,  int data)
{
    if(tree->data==data)
        delete2(tree);
    if(tree->data<data)
        delete1(tree->right,data);
    else if(tree->data>data)
        delete1(tree->left,data);
}

void delete2(node *&tree)
{
    int data;
    node *temp=tree;
    if(tree->right==NULL)
    {
        tree=tree->left;
        delete temp;
    }
    else if(tree->left==NULL)
    {
        tree=tree->right;
        delete temp;
    }
    else
    {
        getpredecessor(tree->left, data);
        tree->data=data;
        delete1(tree->left,data);
    }
}

void getpredecessor(node *tree, int &data)
{
        while(tree->right!=NULL)
            tree=tree->right;
        data=tree->data;
}

int main()
{
    treetype t;
    int ch;
    do
    {
        cout<<"\n\t\tMenu\n1.)Insert\n2.)View\n3.)Delete\n4.)Exit\nEnter choice:-";
        cin>>ch;
        switch(ch)
        {
            case 1:
                int data;
                cout<<"\nEnter the data to be inserted:-";
                cin>>data;
                if(t.finditem(data))
                {
                    cout<<"\nAlready Exists!";
                    break;
                }
                t.insertitem(data);
                break;
            case 2:
                if(t.isempty())
                    cout<<"\nNothing to display!";
                t.viewtree();
                break;
            case 3:
                if(t.isempty())
                    cout<<endl<<"Nothing to delete!";
                else
                {
                    int data;
                    cout<<"\nEnter the data to be deleted:-";
                    cin>>data;
                    if(t.finditem(data))
                        t.deletenode(data);
                    else
                        cout<<"\nDoes not exist!";
                }
                break;
            case 4:
                exit(0);
        }
    }while(1);
}

[Narue]

Be careful with your recursive functions. In your case, delete1 tries to access a dangling pointer because your if chains aren't all connected. Try this instead:

void delete1(node *&tree,  int data)
{
    if(tree->data==data)
        delete2(tree);
    else if(tree->data<data)
        delete1(tree->right,data);
    else if(tree->data>data)
        delete1(tree->left,data);
}

[Nikhar]

Oh...thanks...that worked! So, all my code was missing was was an "else"?

Whoa...I always considered else to be relatively unimportant! But its so freaking important!

Thanks again. :)