Insert of a new node into a binary tree and return its head pointer

Question

Hello i need to make a function that inserts a new node into a binary search tree and returns a pointer to the head/root of that tree. My problem is with the returned value, i cant seem to figure out how to return the head of the tree in a recursive way as seen below.

tree_type insertNode (tree_type tree, int data) {

    tree_type temp = NULL;

    if(!tree)
    {
        temp = (tree_type)malloc(3*sizeof(tree_type)); 

        temp->left = temp->right = NULL;

        temp->data = data;

        tree = temp;

        return ;
    }

    if(data < tree->data)
    {
        insertNode(tree->left, data);
    }
    else if(data > tree->data)
    {
       insertNode(tree->right, data);
    }
}

Answer 1

Firstly, the assignment tree = temp is useless, because tree is a local variable which disappears when the function returns.

Secondly, a return; in a function which is declared as returning a type other than void requires a diagnostic; it is not valid C or C++.

Instead of

tree = temp;
return;

consider returning the new tree:

return temp;

(There is no need for the variable temp; you could just use the variable tree in that case and then return tree).

The problem of how to return the root node is simple:

if(data < tree->data)
{
    tree->left = insertNode(tree->left, data);
    return tree;
}

and so forth. If you eliminate the variable temp and use tree in the malloc case, your function can just have a single return point which consists of return tree;.

If tree->left is null, then insertNode(tree->left, data) receives a null left argument and so receives a new node. We must capture this return value and assign it to tree->left. If tree->left is not null, then insertNode will just return tree->left and so the assignment just writes the same value back into tree->left.

Answer 2

Is that what you need?

if(!tree)
{
    temp = (tree_type) malloc(sizeof(*temp)); 
    temp->left = temp->right = NULL;
    temp->data = data;

    return temp;
}

if(data < tree->data)
{
    tree->left = insertNode(tree->left, data);
    return tree->left;
}
else if(data > tree->data)
{
    tree->right = insertNode(tree->right, data);
    return tree->right;
}