Pointers in recursion not working as expected

Question

I'm trying to do BST insertion;

struct Node
{
    Node* left;
    Node* right;
    int data;

    Node(int d)
        :left(nullptr), right(nullptr), data(d)
    {
    }
};


void Insertion(Node* head, int value)
{
    if (!head)
    {
        head = new Node(value);
        return;
    }

    if (head->data > value)
        Insertion(head->left, value);
    else
        Insertion(head->right, value);
}

void printTree(Node* root)
{
    if (!root)
    {
        return;
    }

    cout << root->data << " "; //20 15 10 18 30 35 34 38
    printTree(root->left);
    printTree(root->right);

}

int main()
{
    Node *root = new Node(20);
    Insertion(root, 15);
    Insertion(root, 30);
    Insertion(root, 10);
    Insertion(root, 18);
    Insertion(root, 35);
    Insertion(root, 34);
    Insertion(root, 38);

    printTree(root);

}

My Insertion method won't insert properly. But if I use it like the following it does;

Node* Insertion(Node* head, int value)
{
    if (!head)
    {
        return (new Node(value));   
    }

    if (head->data > value)
        head->left = Insertion(head->left, value);
    else
        head->right = Insertion(head->right, value);

    return head;
}

I'm not sure if Node* head is a copy of what I'm sending, if it is, is it possible to create the same function without using a Node return type but by passing head by reference?

Remember that arguments in C++ are by default passed *by value*. That means the value used in the call will be *copied* into the functions argument variable, and any modifications to the argument variable (like assignments to it) will be lost when the function returns. Please invest in [some decent books](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list/388282#388282) and read about *references* and how to pass arguments by reference. Case in point: In the `Insertion` function you assign to `head`. That assignment is lost when the function returns. — Some programmer dude, Jan 13 '22 at 06:47
`head` is a value parameter. It's modification will be lost when you return from `Insertion()`. To prevent this, you have to change its type into `Node*& head` - a reference to the node pointer. The alternative could be to apply the return value of `Insertion()` at the call side because this is the updated value of `Node* head` afterwards e.g. `root = Insertion(root, 15);`. — Scheff's Cat, Jan 13 '22 at 06:48
@Scheff'sCat, thank you for `Node*& head` I wasn't aware that pointers could be passed by reference as well. — user2384330, Jan 13 '22 at 07:09
@Someprogrammerdude thank you for the link, I'll try some of the books mentioned there — user2384330, Jan 13 '22 at 07:09
Although not a replacement for buying a good book, here are links to an online tutorial which explain the difference between passing [by value](https://www.tutorialspoint.com/cplusplus/cpp_function_call_by_value.htm), [by pointer](https://www.tutorialspoint.com/cplusplus/cpp_function_call_by_pointer.htm) and [by reference](https://www.tutorialspoint.com/cplusplus/cpp_function_call_by_reference.htm). — Andreas Wenzel, Jan 13 '22 at 07:16

score 1 · Accepted Answer · answered Jan 13 '22 at 07:42

You can use a reference to pointer like mentioned in the comment, or you can also use a pointer to pointer like the following:

void Insertion(Node** head, int value)
{
    if (!(*head))
    {
        *head = new Node(value);
        return;
    }

    if ((*head)->data > value)
        Insertion(&(*head)->left, value);
    else
        Insertion(&(*head)->right, value);
}

And call the function like this:

Node *root = new Node(20);
Insertion(&root, 15);

In your code, you are just copying the address to the function parameter (pointer variable). And inside the function, you are assigning another address to it. But that's not what you want in this case. You need to change the content of the address that you are passing.

Pointers in recursion not working as expected

1 Answers1