CODEWITHSUNDEEP
algorithmc++11data-structuresbinary-search-tree
Mukul Baheti
Mukul Baheti

Reputation: 80

Binary Search Tree Insertion using a void function

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?

Upvotes: 1

Views: 5895

Answers (5)

Samarth H Shivaswamy
Samarth H Shivaswamy

Reputation: 11

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);
    }
}

Upvotes: 1

shubmishra
shubmishra

Reputation: 11

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).

Upvotes: 1

Gayathri
Gayathri

Reputation: 1

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);
            }
        }
    }
}

Upvotes: 0

arunk2
arunk2

Reputation: 2416

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!

Upvotes: 1

Clearer
Clearer

Reputation: 2306

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.

Upvotes: 2

Related Questions