help me please in bst insertion,i think something is wrong in insertion(insert function)

Question

#include<bits/stdc++.h>
using namespace std;
struct node {
int data;
node *left;
node *right;
};
node * init(int data){

node * root=new node();
root->data=data;
root->left=NULL;
root->right=NULL;
return root;
}
void insert(node * root,int x){
if(root==NULL)
{
root=init(x);
// cout<<root->data<<endl;
return ;
}
else if(root->data>x)
insert(root->left,x);
else if(root->data<x)
insert(root->right,x);
}
void printe(node*root){
if(root==NULL)return;
cout<<root->data;
printe(root->left);
printe(root->right);
}
int main(){
int ar[]={5,3,6,4,23,6};
node * root=init(ar[0]);
for(int i=1;i<6;i++){

insert(root,ar[i]);
}
cout<<"print"<<" ";
printe(root);
//cout<<"root->l->data"<<root->left->data<<endl;
}

Answer 1

the root param in insert function is a pointer passed by value then when you modify his value inside it, original param will not be modified (then recursive call to insert will not update the new root->left or root->right pointer)... Try to use pointer passed by reference like:

void insert(node*& root, int x){
.....
}

P.S. Next time, please, when post code longer than 6-7 lines, use "CodePlayground" for save it and post here his link

Answer 2

The pointer its an var containing an adress but has same limits of passing by value then if you have to modify the original var passed like param, you have to use pass by ref... Example:

void nullify(int* p){
p= NULL;
}

void nullifyRef(int*& p){
p= NULL;
}
....
int a= 1;
int* p= &a;

nullify(p);
// p here is always &a and not NULL
// because p its a local variable
// inside nullify then you edit only
// it and not original parameter passed

nullifyRef(p);
// now p is NULL because its passed
// by reference

Answer 3

thank u KrOW

Answer 4

Bahubali Just for info, you can use a pointer to pointer also (eg void insert(node ** root, int x)) but using reference here make all more simple ... Anyway, your are welcome 👍👍👍

Answer 5

https://code.sololearn.com/cSBye27S7t02/?ref=app
here are some change in insert function
also giving right result
my question is since this is also pass by value and also it is returning node but in for loop I am not storing the returned value so how the root is connecting to other nodes

Answer 6

1) Yes... If you dont assign in main the root var, it will be always null

2) Supposing that root its inited before insert calls (in main function) all insertions works because you are modifying a var through a pointer (thats is the adress of that var). This is different from modify original var. root in main is a var then it has a value and an adress. When you pass it to insert function you are passing the VALUE of root (main) not his adress and the value is the adress of a node (or NULL) then from insert function you can modify THAT node but not the value of root (in main). This because you pass it by value

Answer 7

thank u so much for ur time KrOW

Answer 8

You are welcome 👍👍 and i hope that i have clearify some concept

Answer 9

hey I have very silly question
root is a pointer which store the address of a node so I am passing address of that node and connecting all node to that node where I am wrong

Answer 10

Because you have inited root before the loop (with init) and following nodes are assigned in recorsive way... Try to set

node* root= NULL;

and you code will not work anymore

Answer 11

why it is not working if I make root =NULL I scratching my head right now it's been a day I am just digging this algorithm in many ways and coming up with many confusion

Answer 12

Try to follow the logic of insert function... What happen when node root is NULL? It simply create a new node, set the data and return it (in practice its same like init function).
Then if you dont init the original root pointer and not assign inited pointer to it, your call to insert will make always a new node (because root is always NULL)... What you have not understanded? Say to me and i will try to explain

Answer 13

when we make root==NULL insert function return node but we r not assigning that node to root thats make root always null right?
in recursive we are connecting all node to root and return to main so how
is that make change to root?because we r not passing it by reference or
if i make root=insert(root,ar[i]) in for loop it will update the root -i understand this approach