Binary Search Tree with string order

Question

I tried to implement a binary search tree that alphabetically sorts words that are inserted, but the traversal keeps printing the same word that I just put.

I think there should be something wrong with the insert function but I couldn't spot the exact error.

Here's my entire code:

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

#define MAX 10

typedef struct tree_node {
  char *data;
  struct tree_node *left;
  struct tree_node *right;
} tree_node;

tree_node* insert(tree_node* root, tree_node* element) {
  if (root == NULL)
    return element;
  else {
    if (strcmp(element->data, root->data) > 0) {
      if (root->right != NULL)
        root->right = insert(root->right, element);
      else
        root->right = element;   
    }
    else {
      if (root->left != NULL)
        root->left  = insert(root->left, element);
      else
        root->left = element;
    }

    return root;
  }
}

void inorder(tree_node *current_ptr) {
  if (current_ptr != NULL) {
    inorder(current_ptr->left);
    printf("%s ", current_ptr->data);
    inorder(current_ptr->right);
  }
}

tree_node* create_node(char* val) {
  tree_node* temp;
  temp = (tree_node*)malloc(sizeof(tree_node));
  temp->data = malloc(sizeof(char) * MAX);
  temp->data = val;
  temp->left = NULL;
  temp->right = NULL;

  return temp; 
}

int main(void) {
  tree_node *my_root = NULL, *temp_node;

  char* element;
  element = malloc(sizeof(char) * MAX);

  printf("Enter a word to insert in the tree: ");
  scanf("%s", element);

  while(1) {
    temp_node = create_node(element); 

    my_root = insert(my_root, temp_node);
      
    printf("In-order traversal: ");
    inorder(my_root);

    printf("\nEnter a word to insert in the tree: ");
    scanf("%s", element);   
  }

  return 0;
}

Answer 1

In your code you have allocated memory for the element variable only once and then you have passed the pointer to that memory space to all other functions. So basically the char * data of all the nodes in your Binary Tree point to the same memory address. Which is why when you take input in the element variable, the data value in all the nodes changes.

To correct this you need to allocate memory every time you take input from the user.

 while(1) {
    temp_node = create_node(element); 

    my_root = insert(my_root, temp_node);
      
    printf("In-order traversal: ");
    inorder(my_root);

    printf("\nEnter a word to insert in the tree: ");
    element = (char*)malloc(sizeof(char)* MAX); //allocating memory before taking input
    scanf("%s", element);   
  }

And now that you have allocated memory while taking input you need not allocate memory for the char pointer when assigning values in the create_node function.

tree_node* create_node(char* val) {
  tree_node* temp;
  temp = (tree_node*)malloc(sizeof(tree_node));
  // temp->data = malloc(sizeof(char) * MAX); No need for this line anymore
  temp->data = val;
  temp->left = NULL;
  temp->right = NULL;

  return temp; 
}