binary search insert function implementation

[koopey]

the insert function is from jumping into c++ but there is no example implementing it. plz see commented section in int main()

#include <iostream>
using namespace std;

struct node
{
    int key_value;
    node* p_left;
    node* p_right;
};


node* insert (node *p_tree, int key)
{
if ( p_tree == NULL )
{
node* p_new_tree = new node;
p_new_tree->p_left = NULL;
p_new_tree->p_right = NULL;
p_new_tree->key_value = key;
return p_new_tree;
}
if( key < p_tree->key_value )
{
p_tree->p_left = insert( p_tree->p_left, key );
}
else
{
p_tree->p_right = insert( p_tree->p_right, key );
}
return p_tree;
}


int main()
{
    ///there was no sample int main. only insert function
    node* p_tree=NULL;///declaring main head of binary tree
    p_tree=insert(p_tree,5);/// for the first insert function, we have to
                            ///p_tree=
    insert(p_tree,35);///from second one onward, no need to do that. right???
}

[SECMoG1T]

couldn't understand it fully let see if we can get you something better

struct node
{
  int key_val;
  node* p_left;
  node* p_right;
  node(int val, node* left,node* right):key_val(val),p_left(left),p_right(right){}///cstor make work easier
 }

void insert(node*& p_tree,int value)
{
   if(p_tree==nullptr)
   {
      p_tree=new node(value,nullptr,nullptr);
   }

  else
   {
        node* temp=p_tree;

        while(temp!=nullprt)
         {
            if(temp->key_value<value)
                   temp=temp->p_left;
            else
                  temp=temp->p_right;
        }
   
         temp=new node(value,nulptr,nullptr);
   }
}

int main()
{
    node* p_tree=nullptr;
    
    int j=0; ///let's insert 20 values

   while(j<20)
   {
      insert(p_tree,j);
      ++j;
   }
}

edit: sorry i was a little careless din't realize that was a recursive function so here we go:

void insert(node*& p_tree,int value)
{
   if(p_tree==nullptr)
    {
          p_tree=new node(value,nullptr,nullptr);
    }
  
   else if(p_tree.key_value<value)
          insert(value,p_tree->p_left);
   else
          insert(value,p_tree->p_rigth);
}
///on each insert you have to explicitly call the function. 

[koopey]

else if(p_tree.key_value<value)
insert(value,p_tree->p_left);///arguments could well be placed other way 

&

else if(p_tree.key_value<value)///p_tree->key_value 

else, you provided a much better and concise version of required code.

just can't understand,

void insert(node*& p_tree,int value)///why is there '&'. shouldn't it just be '*' as p_tree is a pointer ? 

[SECMoG1T]

p_tree.key_value never mind i just woke up sometimes ago so you can expect that, for the & sign i prefer passing plain pointers by reference to passing them by value coz sometimes they can get nasty ending you up into some serious trouble, so reference could save you some debugging time.

else if(p_tree.key_value<value)
insert(value,p_tree->p_left);///arguments could well be placed other way  

for this am not sure what it means.

[koopey]

for this am not sure what it means.

void insert(node*& p_tree,int value)///your function prototype

insert(value,p_tree->p_left);///arguments here are placed the other way.

but above simple error is reasonable and i

can expect that

since you

just woke up sometimes ago

never mind

never did! ;) thnx.

[fg109]

@koopey

To comment on your original code, insert(p_tree,35);///from second one onward, no need to do that. right??? is wrong. You always need to do p_tree = insert(p_tree,35);. That comes in handy if you're doing AVL trees and need to rotate sub-trees to balance the whole tree.

[SECMoG1T]

Ooh yeah, you got me on that xD, i'll laugh at myself :D

[koopey]

@fg109 i don't quite get what you meant. either 1) commenting in original code is wrong(why???) or 2) while calling insert, i need to always write p_tree= or 3) both?

[fg109]

I meant 2. Since the original function takes a pointer by value and not by reference, the pointer in your main function is not changed unless you use p_tree=.

[koopey]

@fg109 @andy1992 the topic should have been closed by now. sorry for dragging it more but i don't really understand.

i am simply following jumping into c++ now and it, till now, don't have passing pointer by reference/value. so i had to Google it a bit. can't understand the necessity of passing by reference in this case. and @fg109 the necessity of writing p_tree=


example:

int main()
{
    int x=5;
    int* p_x=&x;
    experiment(p_x);///argument p_x and p_y(p_y in prototype function below) both refer to same thing.
    cout<<*p_x;///modifying p_y below changes p_x as well
}
void experiment(int* p_y)
{
    *p_y+=5;///modifying value of p_y
    cout<<*p_y<<endl;
}

contextual to question,

for clarity, let me change insert function's argument's name
node* insert (node *p_dummy_tree, int key)///p_tree changed to p_dummy_tree

1) p_dummy_tree and p_tree(when passed to function) would point to same thing. simply modifying one would modify other. why pointer by reference than simple pointer in this case?

@fg109 2) since modifying p_dummy_tree would change p_tree, why use p_tree=. p_tree itself will change without using p_treethe code seems to work fine without p_tree when i checked.

[fg109]

It's different when you're allocating new memory.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

#include <iostream> using namespace std; void experiment(int*, int val); int main() { int x = 5; int* p_x = &x; cout << "main: " << *p_x << endl; experiment(p_x, 10); cout << "main: " << *p_x << endl; experiment(p_x, 20); cout << "main: " << *p_x << endl; experiment(p_x, 30); cout << "main: " << *p_x << endl; return 0; } void experiment(int* p_y, int val) { p_y = new int(val); cout << "experiment: " << *p_y << endl; }

main: 5 experiment: 10 main: 5 experiment: 20 main: 5 experiment: 30 main: 5

Try adding this to your code in the first post and see what happens:

void display(node *p_tree)
{
    if (p_tree == NULL)
        return;
    display(p_tree->p_left);
    cout << p_tree->key << ' ';
    display(p_tree->p_right);
}