Is binary tree search lying to me?

Question

Hey I'm trying to write a program that will take a list of strings (these are in order):

polymorphism
object
templates
structure
class
pointer
reference
traversal
inheritance
exceptions
recursive
overloading

And then store these strings in a binary tree and finally do an in-order traversal. However, I'm having a problem that I just can't figure out. My function to add nodes keeps telling me that I've already added the node but, it never actually gets added?? My output is like this:

ADDED NODE: polymorphism
ERROR: Same Data: object, object
ERROR: Same Data: templates, templates
ERROR: Same Data: structure, structure
ERROR: Same Data: class, class
ERROR: Same Data: pointer, pointer
(etc...)
ERROR: overloading, overloading
ERROR: overloading, overloading
FINISHED BUILDING

overloading

Finally, here's the source code:

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

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

void buildTree(struct tree**);
void printAlpha(struct tree*);
void insert(struct tree **root, char *n);

int main(int argc, char* argv[]) {
    struct tree* myTree = NULL;

    buildTree(&myTree);
    printf("FINISHED BUILDING\n\n");
    printAlpha(myTree);

    system("PAUSE");
    return 0;
}

/*Builds tree from text file*/
void buildTree(struct tree **root) {
    FILE* fIn = fopen("./in.txt", "r");
    char* input = (char*) malloc(sizeof(char));

    if(!fIn) {
        printf("ERROR: Cannot find file\n");
        return;
    }

    while(!feof(fIn) && fscanf(fIn, "%s", input)) {
        // printf("INP:%s\n", input);
        insert(root, input);
    }
}

void insert(struct tree **root, char *n) {
    if (*root == NULL) {
        // found the spot, create and insert the node
        struct tree *newNode = NULL;
        newNode = (struct tree*) malloc(sizeof(struct tree) );
        newNode->data = n;
        newNode->left = NULL;
        newNode->right = NULL;
        *root = newNode;

        printf("ADDED NODE: %s\n", newNode->data);
    }

    else if(strcmp(n, (*root)->data) < 0)
    insert(&((*root)->left), n);
    else if(strcmp(n, (*root)->data) > 0)
    insert(&((*root)->right), n);
    else
    printf("ERROR: Same data: %s, %s\n", (*root)->data, n);
}

/*In order traversal*/
void printAlpha(struct tree *root) {
    struct tree *curNode = root;

    /*If empty something went wrong*/
    if(!curNode) {
        printf("Error: Binary Tree Is Empty!\n");
        //  return;
    }

    if(curNode->left != NULL) {
        printAlpha(root->left);
    }

    printf("%s\n", curNode->data);

    if(curNode->right != NULL) {
        printAlpha(curNode->right);
    }
}

Answer 1

You are creating a single string (char* input = (char*) malloc(sizeof(char));) and overwriting its contents each time. You insert this single string into the tree, then the next time compare it against itself.

Solution: Move the malloc inside the loop.