Pointers in recursion not working as expected

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?

Solution 1:

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.