2

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 

}
Improve this question
8
  • 2
    Drop this into your debugger and step through it to see where it's misbehaving. Commented Feb 14, 2019 at 19:45
  • 3
    Move the malloc() into the scope of the if (start == NULL ) otherwise every time function insert() is called including recursively you will have a malloc() triggered resulting in unused memory that can not be freed with free(). Commented Feb 14, 2019 at 19:53
  • If you don't have access to a debugger.... you can always add print statements to your functions, to tell you what is happening, what the values of parameters and variables are, and so on Commented Feb 14, 2019 at 19:53
  • Also passing a pointer is passing the value of a pointer. if you want to update the pointer you have to pass the address of a pointer. Commented Feb 14, 2019 at 19:55
  • @RichardChambers unfortunately, moving malloc() into the scope of if(start==null) statement doesnt help Commented Feb 14, 2019 at 19:57

2 Answers 2

Reset to default
1

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);
}
Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Wow, what a pointer action. Great solution, i cant explain how greatful I am. Thanks a lot
@kenshin you're welcome. You can up vote the answer ;)
0

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
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.