data-structurestreebinarybinary-search-treecreation

Why is my create function of binary search tree not working?


The create function is supposed to ask the user how many nodes they want to enter and then insert that many elements one by one.

I am using the pre order traversal function to check the creation of the binary search tree

The code runs fine for the input part, where it is asking the user for data to enter, but when it is supposed to show the tree in pre order traversal manner, it does not do anything and exits.

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

struct Node
{
    int data;
    struct Node* left;
    struct Node* right;
};

void insert(struct Node* root, int x)
{
    if(root -> left == NULL && x < root -> data)
    {
        struct Node* new_node = (struct Node* )malloc(sizeof(struct Node));
        new_node -> data = x;
        new_node -> left = NULL;
        new_node -> right = NULL;
        root -> left = new_node;
    }
    else if(root -> right == NULL && x > root -> data)
    {
        struct Node* new_node = (struct Node* )malloc(sizeof(struct Node));
        new_node -> data = x;
        new_node -> left = NULL;
        new_node -> right = NULL;
        root -> right = new_node;
    }
    else
    {
        if(x < root -> data)
        {
            insert(root -> left, x);
        }
        else if(x > root -> data)
        {
            insert(root -> right, x);
        }
    }
}

void create(struct Node* root)
{
    root = (struct Node*)malloc(sizeof(struct Node));
    printf("\nHow many nodes do you want to create: ");
    int tree_size;
    scanf("%d", &tree_size);
    printf("\nEnter data for root node: ");
    int ent_data;
    scanf("%d", &ent_data);
    root -> data = ent_data;
    root -> left = NULL;
    root -> right = NULL;
    for(int i=1; i<tree_size; i++)
    {
        printf("\nEnter data for node: ");
        scanf("%d", &ent_data);
        insert(root, ent_data);
    }
}

void preOrderTraversal(struct Node *root)
{
    if(root != NULL)
    {
        printf("%d, ", root -> data);
        preOrderTraversal(root -> left);
        preOrderTraversal(root -> right);    
    }
}


int main()
{
    struct Node* root = NULL;
    create(root);
    
    preOrderTraversal(root);
    return 0;
}

Solution

  • The problem is that create is not going to modify your main's variable root. C arguments are passed by value, so you should do one of the following:

    The second option is to be preferred, because root does not serve as input value for create, but as output.

    Not related to your issue, but try to avoid code repetition. There are three places in your code where you call malloc and initialise a node. instead create a function for that and call it at those three places.

    Here is the adapted code:

    #include <stdio.h>
    #include <stdlib.h>
    
    struct Node
    {
        int data;
        struct Node* left;
        struct Node* right;
    };
    
    // Function to call whenever you need a node instance
    struct Node * create_node(int x)
    {
        struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
        new_node -> data = x;
        new_node -> left = NULL;
        new_node -> right = NULL;
        return new_node;
    }
    
    void insert(struct Node* root, int x)
    {
        if(root -> left == NULL && x < root -> data)
        {
            root -> left = create_node(x); // Use function
        }
        else if(root -> right == NULL && x > root -> data)
        {
            root -> right = create_node(x); // Use function
        }
        else
        {
            if(x < root -> data)
            {
                insert(root -> left, x);
            }
            else if(x > root -> data)
            {
                insert(root -> right, x);
            }
        }
    }
    
    struct Node* create() // No parameter, but return type
    {
        printf("\nHow many nodes do you want to create: ");
        int tree_size;
        scanf("%d", &tree_size);
        printf("\nEnter data for root node: ");
        int ent_data;
        scanf("%d", &ent_data);
        struct Node* root = create_node(ent_data); // Use function
        for(int i=1; i<tree_size; i++)
        {
            printf("\nEnter data for node: ");
            scanf("%d", &ent_data);
            insert(root, ent_data);
        }
        return root; // Return the root
    }
    
    void preOrderTraversal(struct Node *root)
    {
        if(root != NULL)
        {
            printf("%d, ", root -> data);
            preOrderTraversal(root -> left);
            preOrderTraversal(root -> right);    
        }
    }
    
    
    int main()
    {
        struct Node* root = create(); // No argument, but return value
        preOrderTraversal(root);
        return 0;
    }