Binary Search Tree Insertion using a void function

Question

I have written two different codes for inserting into a binary tree, one works whereas other doesn't.

This is how my node looks:

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

The following is the code for node* newnode(int a)

node* newnode(int a)
{
    node *temp=new node;
    temp->data=a;
    temp->left=nullptr;
    temp->right=nullptr;
    return temp;
}

And following are the two different codes for insertion:

This one returns a pointer to the node:

 node* insertion(node *root, int a)
 {
    if(root==nullptr)
        return newnode(a);
    else if(a<root->data)
        root->left=insertion(root->left, a);
    else
        root->right=insertion(root->right, a);
 }

This one returns void:

void insertion2(node *root,int a)
{
    if(root==nullptr)
        root=newnode(a);
    else if(a<root->data)
        insertion2(root->left,a);
    else
        insertion2(root->right,a);
}

The one which returns void doesn't work. And as per the analysis I made, after the function call, root is still nullptr. Can anyone explain me why does it not work?

Here `root` is modified in the function, which will have no effect on the `root` in the main. The above function call modifies the variable local to the function, which has no effect overall — GAURANG VYAS, Jun 15 '17 at 10:54
I figured that would be the problem but then I thought that passing a function parameter as a pointer is a method of pass by reference. Hence any changes made to `root` in function `insertion2` should be visible in `main` as well (`root` is a pointer to `node`). Or have I got it all wrong? — Mukul Baheti, Jun 15 '17 at 11:03
No, it is not the case here. Look if you make any changes to the data pointed by `root` (something like `*root = something`) then only it is visible in the `main's` copy of `root`, but here you are making change to `root` itself. Here address itself is passed by value, so any changes made to `root` will be local to the function. — GAURANG VYAS, Jun 15 '17 at 11:14
`insertion` is definitely broken as well. There is no `return` for any branch where `root ! =nullptr`, so the behaviour is undefined. — eerorika, Jun 15 '17 at 12:19
You may want to accept one of the answers given. Just out of curtsey to the people who answered. — Clearer, Jun 16 '17 at 06:18

score 2 · Accepted Answer · answered Jun 15 '17 at 10:47

2

Notice that in the insertionversion you have root->left = insertion(root->left, a) and root->right = insertion(root->right, a), but you have nothing to the same effect in insertion2. In effect, insertion2 does nothing except leak memory.

answered Jun 15 '17 at 10:47

Clearer

2,166
23
38

But in the `if-else` case I am passing `root->left` or `root->right` as one the parameters. Hence when the function is called if lets say `root->left` is `nullptr` then woudn't it be same as `root->left=newnode(a)` as now `root->left` has become `root`? – Mukul Baheti Jun 15 '17 at 10:55
In `insertion` I am returning `newnode(a)`. Hence function returns me a pointer to that new node which gets saved in the `root`. Whereas in `insertion2` I am saving `newnode(a)` in the function itself. So aren't both effectively same? Like isn't `root=insertion(root,3); insertion(root,5); insertion(root,10);` same as `insertion2(root,3); insertion2(root,5); insertion2(root,10);` (as in the function itslelf there is a line which says `root=newnode(a)`) ? – Mukul Baheti Jun 15 '17 at 10:59
In the second version, you're never writing anything to root->left or root->right, you are writing to a variable name root, but not to the object it points to. – Clearer Jun 15 '17 at 11:03
Finally understood. In order to make `insertion2` work I had to make the following change: `void insertion2(node *&root, int a)`. After this change, the code works smoothly. – Mukul Baheti Jun 15 '17 at 12:12

score 1 · Answer 2 · answered Jun 15 '17 at 12:50

To answer your question.

The problem with your insertion2 function is that the root variable will point to nullptr(NULL) at the called place and a new memory is allocated and pointed to a local reference inside insertion2() function. The reference change to a new memory location will not have any impact on the reference @ calling place. As pointed by others, this call will always leak memory in @clearer answer.

To make this function to work. Move the object creation part @ calling place and leave just the insert to this function.

something like the below should work.

void insertion2(node *root, node *new_node)
{
    if(root==nullptr)
        root=new_node;
    else if(a<root->data)
        insertion2(root->left,new_node);
    else
        insertion2(root->right,new_node);
}

// Create the new node and call the insert function
new_node = newnode(a);
insertion2(root, new_node);

Hope it clarifies your doubt!

score 1 · Answer 3 · edited Mar 15 '19 at 17:24

1

in 2nd function root is always a local variable so updating it doesn't change main root variable, since the pointer itself is not passed by reference. You can achieve this by using call by reference, just change your function heading as follows: void insertion2(node *&root,int a).

edited Mar 15 '19 at 17:24

Guillaume Racicot

39,621
9
77
141

answered Mar 15 '19 at 17:03

shubmishra

11
2

score 0 · Answer 4 · edited Sep 18 '18 at 16:19

This way is working fine while using void return type. Declare a global variable, first.. it is set to one if the node to be inserted is first.. later change it to 0.

void insertRoot(struct node* newnode){
    root=newnode;
}

void insert(struct node* root, int data)
{
    if(first==1){
            insertRoot(createNode(data));
            first=0;
    }else{
        if (data < root->data){
            if(root->left==NULL){
                root->left=createNode(data);
            }else{
                insert(root->left,data);
            }
        }
        else if (data > root->data){
            if(root->right==NULL){
                root->right=createNode(data);
            }else{
                insert(root->right,data);
            }
        }
    }
}

score 0 · Answer 5 · answered Sep 22 '19 at 18:59

The Root pointer from the calling method needs to be updated as well. So, you'll have to call the Insert2 method using something similar: Insert2(&BSTNodePtr, a). When you pass the address of the variable BSTNodePtr, the Insert2 method can update it's content.

Try this instead:

void Insert2(BSTNode **root, int a){
    if (*root==NULL){
        *root = new BSTNode(a);
    }
    else if (a<= (*root)->data){
        Insert2(&((*root)->left), a);
    }
    else{
        Insert2(&((*root)->right), a);
    }
}

Binary Search Tree Insertion using a void function

5 Answers5

Linked