Error in insert function for binary search tree

Question

I tried compiling this program in codeblocks but it gives an error message

cannot convert void to treenode

(in the insert function), though I have specified declared t in the parameter part itself. I tried removing that line, but the program didn't give any output. Any suggestions?

#include<iostream>
#include<malloc.h>
using namespace std;
struct treenode;
typedef struct treenode *position;
typedef struct treenode *searchtree;
typedef int elementtype;
position find(elementtype x,searchtree t);
position findmin(searchtree t);
position findmax(searchtree t);
searchtree insert(elementtype x,searchtree t);
searchtree delete1(elementtype x,searchtree t);
struct treenode
{
    elementtype element;
    searchtree left;
    searchtree right;
};
position find(elementtype x,searchtree t)
{
    if(t==NULL)
        return NULL;
    else if(x<t->element)
        return find(x,t->left);
    else if(x>t->element)
        return find(x,t->right);
    else
        return t;
}
position findmin(searchtree t)
{
    if(t==NULL)
        return NULL;
    else if(t->left==NULL)
        return t;
    else
        return findmin(t->left);
}
position findmax(searchtree t)
{
    if(t!=NULL)
        while(t->right!=NULL)
            t=t->right;
    return t;
}
searchtree insert(elementtype x,searchtree t)
{
    if(t==NULL)
    {
        t=malloc(sizeof(struct treenode)); //gives me error on compiling
        if(t==NULL)
        {
            cout<<"\n Out of space";
            exit(0);
        }
        t->element=x;
        t->right=t->left=NULL;
    }
    else if(x<t->element)
        t->left=insert(x,t->left);
    else if(x>t->element)
        t->right=insert(x,t->right);
    return t;
}
void display(searchtree t)
{
    if(t==NULL)
        return;
    display(t->left);
    cout<<t->element;
    display(t->right);
}
searchtree deletion(elementtype x,searchtree t)
{
    position tmpcell;
    if(t==NULL)
    {
        cout<<"\nElement not found";
        return NULL;
    }
    else if(x<t->element)
        t->left=deletion(x,t->left);
    else if(x>t->element)
        t->right=deletion(x,t->right);
    else if(t->left && t->right)
    {
        tmpcell=findmin(t->right);
        t->element=tmpcell->element;
        t->right=deletion(t->element,t->right);
    }
    else
    {
        tmpcell=t;
        if(t->left==NULL)
            t=t->right;
        else if(t->right==NULL)
            t=t->left;
        free(tmpcell);
    }
    return t;
}
int main()
{
    int ch,x;
    position p;
    searchtree t=NULL,min,max;
    while(1)
    {
        cout<<"\n1. Insert\n2. Delete\n3.Find min\n4. Find max\n5. Display\n6. Exit";
        cout<<"\nEnter your choice:";
        cin>>ch;
        switch(ch)
        {
        case 1:
            cout<<"\nEnter the element:";
            cin>>x;
            t=insert(x,t);
            break;
        case 2:
            cout<<"\nEnter the element to be deleted:";
            cin>>x;
            t=deletion(x,t);
            break;
        case 3:
            min=findmin(t);
            if(min)
                cout<<"\nMinimum element is "<<min->element;
            else
                cout<<"\nEmpty tree";
            break;
        case 4:
            max=findmax(t);
            if(max)
                cout<<"\nMaximum element is "<<max->element;
            else
                cout<<"\nEmpty tree";
            break;
        case 5:
            display(t);
            break;
        case 6:
            exit(0);
        default :
            cout<<"\nWrong choice";
        }
    }
    return 0;
}

Answer 1

In C pointer void * is automatically and safely promoted to any other pointer type. So, it is not required to cast malloc ouput to your pointer, for example Do I cast the result of malloc?

However, in C++ it is required to cast output of malloc(), for example Why does C++ require a cast for malloc() but C doesn't?

Since you are using C++ you have to explicitly cast void* pointer to required pointer type:

// valid in C, but not valid in C++
struct treenode *t = malloc(sizeof(struct treenode));

// C++
t = (searchtree)(malloc(sizeof(struct treenode)));
// or
t = (struct treenode*)(malloc(sizeof(struct treenode)));
// or
t = static_cast<searchtree>(malloc(sizeof(struct treenode)));

Of course for C++ it makes sense to consider usage of native C++ features. You are allocating memory for one structure instance, so new can be used:

t = new treenode; // instead of malloc
...
delete tmpcell; // instead of free(tmpcell);