Inserting nodes in a binary search tree (C)

binary-search-treec

I'm trying to write a function to insert a node to a binary search tree, and I have the following:

typedef struct Node {
    int key;
    struct Node *left;
    struct Node *right;
} Node;

Node *createNode(int key)
{
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->key = key;
    newNode->left = NULL;
    newNode->right = NULL;

    return newNode;
}

Node *insert(Node *node, int key)
{
    if (node==NULL)
    {
        node = createNode(key);
    }
    else
    {
        if (node->key > key)
        {
            node->left = insert(node->left, key);
        }
        else
        {
            node->right = insert(node->right, key);
        }
    }
    return node;
}

int main(int argc, char* argv[])
{
    Node *root = NULL;
    root = insert(root, 10);

    return 0;
}

I know this works, and if I want to insert 5 to the tree with root node root, I can write root = insert(root, 5);. My question is, how can I write another version of insert that can achieve the same thing with simply insert(root, 5);? I have tried the following but with no avail.

void insert(Node *node, int key)
{
    if (node==NULL)
    {
        node = createNode(key);
    }
    else
    {
        if (node->key > key)
        {
            insert(node->left, key);
        }
        else
        {
            insert(node->right, key);
        }
    }
}

What is wrong with this and why doesn't this work?. Any pointers (no pun intended) would be greatly appreciated!

Best Answer

For me, your first solution is elegant.

Now, if you want to insert without taking advantage of return value, then a way could be using a pointer to pointer.

Something like:

void insert(Node ** node, int key)
{
    if (*node == NULL)
      *node = createNode(key);
    else if ((*node)->key > key)
      insert(&(*node)->left, key);
    else
      insert(&(*node)->right, key);
}

And the call would be

insert(&root, 10);
Related Topic