Inserting data into binary tree in C

Question

So basicaly I was working on a simple program to insert data to a binary tree. The program calls the function for a integer variable of 15 which will be the head node, and then the same function is called for a variable of 12, which should implement the new data on the left branch of the root node. Unfortunately although the first part works correctly, and the root node is printed out, than when the new value should be implemented for the left branch of the root node, nothing happens. Any tips and suggestions are welcome. Thanks.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct node
{
    int data;
    struct node *right;
    struct node *left;
} NODE;
void *insert(int ins, NODE *start)
{
    NODE *newNode = malloc(sizeof(NODE));
    if (start == NULL )
    {
        newNode->data = ins;
        newNode->left = NULL;
        newNode->right = NULL;

    }
    if(ins<start->data)
    {
        insert(ins, start->left);
    }
    else if(ins>start->data)
    {
        insert(ins, start->right);
    }
}
int main()
{  
    int number;
    NODE *head;
    head=NULL;

    number = 15;
    head = insert(number, head);
    printf("prints the first element (head): %d", head->data);

    number = 12;
    insert(number, head);

    printf("should print the left branch : %d", head->left->data);  // <- THIS DOES NOT SHOW UP 

}

Answer 1

It looks like the following is close to what you want.

This is a recursive insert() function which takes the address of a node and looks to see if it should either add a new node into the tree or to take a branch to continue looking for the place to do a node insertion.

One thing to also consider is what if the value already exists in the tree. In this case we just skip it and assume that the tree should contain unique values only.

I'm not really up on tree lore so I'm not sure what kind of binary tree this is or traversal, etc. I'll leave that up to you.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct node
{
    int data;
    struct node *right;
    struct node *left;
} NODE;

void *insert(int ins, NODE **start)
{
    if (*start == NULL)
    {
        NODE *newNode = malloc(sizeof(NODE));

        newNode->data = ins;
        newNode->left = NULL;
        newNode->right = NULL;

        (*start) = newNode;

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

    // if we already have this value in the tree then we will do nothing
    // and ignore it.
    return *start;
}

void printTree(NODE *start)
{
    // print tree
    if (start->left) printTree(start->left);
    printf("Element value %d\n", start->data);
    if (start->right) printTree(start->right);
}

int main ()
{
    int number;
    NODE *phead = NULL;

    number = 15;
    insert(number, &phead);
//  printf("prints the first element (head): %d", head.data);

    number = 12;
    insert(number, &phead);

//  printf("should print the left branch : %d", head.left->data);  // <- THIS DOES NOT SHOW UP 

    number = 22;
    insert(number, &phead);

    number = 48;
    insert(number, &phead);

    number = 33;
    insert(number, &phead);

    // try a duplicate node data.
    number = 48;
    insert(number, &phead);

    printTree(phead);
    return 0;
}

The output generated is:

Element value 12
Element value 15
Element value 22
Element value 33
Element value 48

Answer 2

The start parameter is passed by value, so it is never modified. One of the options you have is passing a pointer to a pointer of NODE, like this:

void insert(int ins, NODE **start)
{
    if (*start == NULL )
    {
      NODE *newNode = (NODE *)malloc(sizeof(NODE));
      newNode->data = ins;
      newNode->left = NULL;
      newNode->right = NULL;
      *start = newNode;
    }
    if(ins< (*start)->data)
    {
      insert(ins, &(*start)->left);
    }
    else if(ins> (*start)->data)
    {
      insert(ins, &(*start)->right);
    }
}

int main()
{

    int number;
    NODE *head;
    head=NULL;

    number = 15;
    insert(number, &head); ///Doesn't need head=insert(...) anymore
    printf("prints the first element (head): %d", head->data);

    number = 12;
    insert(number, &head);

    printf("should print the left branch : %d", head->left->data);
}