BST implementation

Question

What's wrong with the following implementation of a binary search tree (BST)? I have been told that it is better to use pointer to a pointer to struct node as an argument in insert function.

struct node
{
int key_value;
struct node* left;
struct node* right;
};

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 );
    }
}

Answer 1

When a node is inserted (leaf == 0), you didn't change its parent, so the new node will become an orphan.

In other words, your tree will still look like only one node, no matter how many nodes were called with insert.

Answer 2

This line:

leaf = (struct node*) malloc( sizeof( struct node ) );

gives a new value to leaf, pointing it at some newly allocated memory. However, the new value does not leave the function. When the fuction returns, the caller will still be referring to the old leaf, and there will be a memory leak.

There are two approaches you could take to fixing it:

1. Use a pointer to a pointer, e.g.

void insert(int key, struct node **leaf)
{
    if(*leaf == 0 )
    {
        *leaf = (struct node*) malloc( sizeof( struct node ) );
        ...
}

/* In caller -- & is prepended to current_leaf. */
insert(37, &current_leaf);

2. Return the new leaf (or the old leaf if there is no change).

struct node *insert(int key, struct node *leaf)
{
    if(leaf == 0 )
    {
        leaf = (struct node*) malloc( sizeof( struct node ) );
        ...
    }

    return leaf;
}

/* In caller -- & is prepended to current_leaf. */
current_leaf = insert(37, current_leaf);

Pointers to pointers are close to the threshold of being hard to comprehend. I would probably go for the second option, if insert isn't currently returning anything else.