Jump to content

» «

Binary tree Insertion pointer to pointer?

2 replies to this topic
  • Swoorup

    Foot Soldier

  • Feroci
  • Joined: 28 Oct 2008
  • Nepal


Posted 24 December 2011 - 04:16 PM

I have been studying this for two hours but I don't just get why a pointer to pointer is used for the second parameter? Could not it do with only *leaf? The cprogramming site mentions that it is done so in order to allow memory allocation for root node also but could it do with only a single pointer?

Here's the code that account what I have said:

insert(int key, struct node *leaf)
   if( leaf == 0 )
       leaf = malloc( sizeof( struct node ) );
       leaf->key_value = key;
       leaf->left = 0;    
       leaf->right = 0;  
   else if(key < leaf->key_value)
       insert( key, leaf->left );
   else if(key > leaf->key_value)
       insert( key, leaf->right );

And the actual code:
insert(int key, struct node **leaf)
   if( *leaf == 0 )
       *leaf = (struct node*) malloc( sizeof( struct node ) );
       (*leaf)->key_value = key;
       /* initialize the children to null */
       (*leaf)->left = 0;    
       (*leaf)->right = 0;  
   else if(key < (*leaf)->key_value)
       insert( key, &(*leaf)->left );
   else if(key > (*leaf)->key_value)
       insert( key, &(*leaf)->right );

Can anyone explain it to me,why is it so?

  • K^2

    Vidi Vici Veni

  • Moderator
  • Joined: 14 Apr 2004
  • United-States
  • Best Poster in Technology / Programming 2017
    Best Poster [Technology / Programming] 2016
    Best Poster [Programming] 2015
    Most Knowledgeable [Web Development/Programming] 2013
    Most Knowledgeable [GTA Series] 2011
    Best Debater 2010


Posted 24 December 2011 - 06:44 PM

Lets look at the first code block you posted. Suppose with this definition of insert(), I call the following:

node *root=0; //Empty tree.
insert(42, root);

The variable root is located at some address, say Address1. At Address1 the value of root is stored, which is 0. In other words *(Address1)=0. Now you make the call. The value from variable root is passed to the function along with the key. The key is stored in variable key, the value from root is stored in variable leaf. Variable leaf is also located somewhere in memory for duration of the call. (Specifically, in the stack, but that's details.) Lets say, leaf is located at Address2. You pass to it the value from root, so effectively you do *(Address2)=*(Address1).

Next, function checks the variable leaf, sees that it is zero, and proceeds to allocate space. You call malloc, and lets say it returns Address3. You set it to leaf. Effectively, *(Address2)=Address3. Then you do other stuff and return from function. So now *(Address2) holds the address to new root node, but *(Address1) was never changed. It is still zero. So after the function exits, root still holds 0. Null pointer, and therefore, useless. The tree was created and lost.

Now lets look at second definition. Call changes only slightly.

node *root=0;
insert(42, &root);

But what happens on the inside? Instead of setting leaf to value of root, you set it to address of root. (The variable itself, not where it points to.) In other words *(Address2)=Address1. Now *leaf=malloc() effectively becomes *(*(Address2)) = Address3. But *(Address2) is same as Address1, so this line is equivalent to *(Address1)=Address3. The rest of the program flows pretty much the same, but after the function returns, root is set to Address3, which is the actual address of the root of your tree.

There are other ways to do all this. For example, you can use return value. Consider the following code.

node *insert(int key, node *leaf)
      return leaf;
      leaf->left=insert(key, leaf->left);
      return leaf;
   leaf->right=insert(key, leaf->right);
   return leaf;

And you'd make the call like this.

node *root=0;
root=insert(42, root);

In terms of efficiency, there is not much difference. Note that I omitted else statements, because code execution never gets past return statements. Sometimes you want to keep the else blocks for clarity, though. This might actually be one of these, but meh.

  • businesslogoart

    Player Hater

  • Joined: 11 Jan 2012


Posted 11 January 2012 - 12:24 PM Edited by Seddo, 11 January 2012 - 11:46 PM.

Good Info, Thanks a lot for this it has helped me a great deal keep it up .

1 user(s) are reading this topic

0 members, 1 guests, 0 anonymous users