CODEWITHSUNDEEP
cbinary-search-tree
Kevin Hsu
Kevin Hsu

Reputation: 153

Inserting nodes in a binary search tree (C)

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!

Upvotes: 3

Views: 21717

Answers (1)

lrleon
lrleon

Reputation: 2648

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

Upvotes: 6

Related Questions