Why does this program always print the same node from a binary search tree

Question

I have this modular program that should store a text file line by line and store each line as a string in each node of a binary search tree, we have to use a binary search tree for the assignment. Then when the user is prompted to enter a word, e.g. "Bus" it should print any string which contain the word bus. But whichever word I input, it always prints the last line of the text file (last string put in to the BST):

Enter word to search for a phone number: Bus
General enquires 01179222000 

phone.txt:

Household waste and street maintenance 01179222100
Textphone for deaf people only   01173574444
Council housing 01179222200
Housing benefit and council tax reduction 01179222300
Council tax 01179222900
Electoral services 01179223400
Planning and building regulations 01179223000
Home Choice Bristol 01179222400
Pest control and dog wardens pollution and public safety 01179222500
report anti social behaviour and nuisance 01179222500
Bus passes and disabled parking permits 0117 922 2600
Residents parking permits 01179222600
Adult care and social services 01179222700
Transport and streets 01179222100
Register office 01179222800
Business rates 01179223300
Highways 01179222100
General enquires 01179222000

map.h

#include <stdbool.h>
// node structure
struct node;
// tree wrapper structure
struct tree;
typedef struct tree Tree;
typedef struct node Node;
// creates a new tree
Tree *new_tree();
// create a new node
Node *NewNode(char *data);
// insert in to the binary tree
Node *insert(Node *node, char *data);
// search for nodes to see if they exist
bool NodeSearch(Node *node, char *data);

map.c

// Binary search tree implementation
#include <stdio.h>
#include <stdlib.h>
#include "map.h"

struct node {
    char *data;
    struct node *left;
    struct node *right;
} ;

// tree wrapper structure
struct tree {
    struct node *root;
} ;

//create a new tree
Tree *new_tree() {
    Tree *t = malloc(sizeof(Tree));
    t->root = NULL;
    return t;
}

//create a new node
Node *NewNode(char *data) {
    Node *node = malloc(sizeof *node);
    node->data = malloc(sizeof data);
    node->left = NULL;
    node->right = NULL;
    return(node);
}

// insert in to the binary tree
Node *insert(Node *node, char *data) {
    // 1. If the tree is empty, return a new, single node
    if (node == NULL) {
        return (NewNode(data));
    }
    else {
    // 2. Otherwise, recur down the tree
        if (data <= node->data)
            node->left = insert(node->left, data);
        else
            node->right = insert(node->right, data);
        return (node); // return the (unchanged) node pointer
    }
}
// search for nodes to see if they exist
bool NodeSearch(Node* node,char *data) {
    if (node == NULL) 
        return false;
    else if(node->data == data) 
        return true;
    else if(data <= node->data) 
        return NodeSearch(node->left, data);
    else 
        return NodeSearch(node->right, data);
}

mainphone.c

#include "map.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stddef.h>
int main() {
    new_tree();
    Node *node = NULL;
    FILE *f;
    char s[300];

    f = fopen("phone.txt", "r");
    while (fgets(s, 300, f) != NULL);
        NewNode(s);
    insert(node, s);

    printf("Enter a word to search for a phone number: ");
    char word[100];
    scanf("%s", word);
    NodeSearch(node, word);

    if (strstr(word, s) == NULL) {
        printf("%s\n", s);
    }
    else {
        printf("ERROR\n");
    }
    fclose(f);
    return 0;
}

Answer 1

The most important mistake I can find after fixing the code formatting which was very unreadable is,

while (fgets(s, 300, f) != NULL);
//                              ^ I don't think so

it's very unlikely that the semicolon was intentional.

The very reason for such a mistake is of course that your code is a mess, but there are other mistakes too.

1. This allocation seems to be wrong because it does not make sense

   node->data = malloc(sizeof data);
   

   this will allocate space to hold a pointer, sizeof data is probably 8 or 4, I don't think you want that but rather

   node->data = malloc(1 + strlen(data));
   

2. You always assume that the allocation was successful, you must check if malloc() returns NULL which indicates a problem, most commonly that there is not enough available memory to allocate.

3. When you create a node you never copy the actual data into the data field of your structure, you should at least do something like this

   size_t length;
   length = strlen(data);
   node->data = malloc(length + 1);
   if (node->data != NULL)
       memcpy(node->data, data, length + 1);
   else
       warn_about_memory_allocation_issue();
   

   if let this go, and ignore the error then you should alwash check the data field for NULL before dereferencing it.

4. If you intend to create a sorted list, this will not work

   if (data <= node->data)
       node->left = insert(node->left, data);
   else
       node->right = insert(node->right, data);
   return node;
   

   because you are comparing the addresses of the involved pointers, not the strings. You need strcmp() instead

   if (strcmp(data, node->data) < 0)
       node->left = insert(node->left, data);
   else
       node->right = insert(node->right, data);
   return node;