Lets look at the first code block you posted. Suppose with this definition of insert(), I call the following:
| CODE |
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.
| CODE |
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.
| CODE |
node *insert(int key, node *leaf)
{
if(!leaf)
{
leaf=malloc(sizeof(node));
leaf->key_value=key;
leaf->left=0;
leaf->right=0;
return leaf;
}
if(key<leaf->key_value)
{
leaf->left=insert(key, leaf->left);
return leaf;
}
leaf->right=insert(key, leaf->right);
return leaf;
} |
And you'd make the call like this.
| CODE |
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.
