binary tree recursive insertion with pointer to pointer

Question

void insert(node ** tree, int val)
{
    node *temp = NULL;
    if(!(*tree))
    {
        temp = (node *)malloc(sizeof(node));
        temp->left = temp->right = NULL;
        temp->data = val;
        *tree = temp;
        return;
    }

    if(val < (*tree)->data)
    {
        insert(&(*tree)->left, val);
    }
    else if(val > (*tree)->data)
    {
        insert(&(*tree)->right, val);
    }
}

This function uses a pointer to pointer node ** tree to represent the head of the binary tree. I came across the same method on many tutorials and websites. I wanted to know why everyone insists on using pointer to pointer and why not just 'node * tree'. I presume even pointer to head of tree would do the job just fine, and using just pointer to head of the tree the recursive calls would be as follows (please correct me if i am wrong):

insert(tree->left, val); // assuming definisiton as void insert(node *tree, int val);

or

insert(tree->right, val); // assuming definisiton as void insert(node *tree, int val);

Please correct me if my understanding is wrong. I am a newbie. Thanks.

Also, [in C don't cast the return of `malloc`](http://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc). — Some programmer dude, Jul 28 '14 at 06:40
FYI the non-recursive version of said-same [can be seen here](http://pastebin.com/Tx7T8cPT) — WhozCraig, Jul 28 '14 at 07:32

Some programmer dude · Accepted Answer · 2014-07-28T07:12:53.960

1

Remember that in C arguments are passed by value, that means the value of the expression you pass as argument is copied into the function. So if you change an argument inside a function, you change only the copy and the change will not be visible to the caller (i.e. the change is lost).

To overcome that problem, you can simulate pass by reference by passing a pointer instead. And if you want to change a pointer, you have therefore pass a pointer to the pointer.

If you look in the insert function, you will see that it assigns to the pointer when *tree is NULL (i.e. there is no node). That would not work if you didn't pass a pointer to a pointer to the node.

Stupid example:

#include <stdio.h>

void func1(const char *s)
{
    s = "hello from func1";
}

void func2(const char **s)
{
    *s = "hello from func2";
}

int main(void)
{
    const char *s1 = "foo";
    const char *s2 = "bar";

    func1(s1);   /* Passing pointer by value */
    func2(&s2);  /* Passing pointer by "reference" */

    printf("s1 = \"%s\"\n", s1);
    printf("s2 = \"%s\"\n", s2);
}

The above little example program will print

s1 = "foo"
s2 = "hello from func2"

edited Jul 28 '14 at 07:12

answered Jul 28 '14 at 06:40

Some programmer dude

400,186
35
402
621

if we had passed pointer to the head i.e. node * tree, we could check for null pointer as tree != NULL , isnt it?? – CodeWithPride Jul 28 '14 at 07:05
@CodeWithPride The problem isn't about checking for `NULL`, it's the *assignment*. – Some programmer dude Jul 28 '14 at 07:10
@CodeWithPride I added a small and simple example to my answer to show the difference. – Some programmer dude Jul 28 '14 at 07:13
thanks for the example.. makes it clear now.. thanks a lot :) – CodeWithPride Jul 28 '14 at 07:20

score 0 · Answer 2 · answered Jul 28 '14 at 06:39

0

That's because the tree can be empty (NULL). In this case, you can set the outside pointer to make it point to the new root.

node *root = NULL;
insert(root, 10);

answered Jul 28 '14 at 06:39

Eric Z

14,327
7
45
69

score 0 · Answer 3 · answered Jul 30 '14 at 09:28

Two types of passing to a function:

1. Pass by value = creates a copy of the value. any change to the value will be lost once the function terminates.

2. Pass by reference = doesn't create a copy but is pointing to the value being passed. If there are changes happen, then the value will change.

Double pointer (**) point to the address of a single pointer(*). Therefore you need to use double pointer in order to change the value (address) of the single pointer if you pass it to a function. Otherwise, theres no change.

binary tree recursive insertion with pointer to pointer

3 Answers3