C - Receiving a SIGABRT when freeing structs - System-specific?

Question

I'm currently tinkering with binary trees in C, but I've run into an issue that I can't seem to solve on my own. I'm using Eclipse Mars as my IDE.

The basic idea of the project is to have a binary tree composed out of treeNodes. These nodes are structs and contain a struct within (struct Books), thus there are two separate libs for treeNode and books.

These are the structs in question:

TreeNode:

struct TreeNode {
    struct Book *book;
    unsigned long key;
    struct TreeNode *left;
    struct TreeNode *right;
};

Book:

struct Book {
    unsigned long ISBN;
    char* author_name;
    char* book_title;
};    

Now, the nodes get created fine and the insertion/print functions work well. However, I also have a clear() function, that is supposed to free any previously allocated memory. Malloc is called only in the new_xxx() functions:

struct TreeNode *new_tree_node(unsigned long ISBN, char *author, char *title) {
    //Creating and allocating the new TreeNode
    struct TreeNode *new_tree_node;
    new_tree_node = (struct TreeNode*) malloc(sizeof(struct TreeNode));

    //Creating the book
    struct Book *new_Book = newBook(ISBN, author, title); 

    new_tree_node->book = new_Book;

    new_tree_node->left = NULL;
    new_tree_node->right = NULL;

    new_tree_node->key = ISBN;

    return new_tree_node;
}

And newBook():

struct Book *newBook(unsigned long ISBN_nr, char *author_name, char *book_title) {
    //Creating and allocating the Book
    struct Book *new_Book;
    new_Book = (struct Book*) malloc(sizeof(struct Book));

    //Assigning Values
    new_Book->ISBN = ISBN_nr;
    new_Book->author_name = author_name;
    new_Book->book_title = book_title;

    return new_Book;
}

Now, when I try to run the clear() function, I receive a "SIGABRT:Aborted" signal as soon as I try to free a TreeNode and the process halts. Eclipse also returns:

"No source available for "raise() at 0x75ffff7a4bcc9".

Initially I thought this happened because my system could not find one of the standard functions, but the console also prints:

*** Error in /home/max/workspace/bst_2/Debug/bst_2': double free or corruption (out): 0x00007fffffffe030 ***

which makes me believe that there actually is an issue within the code.

This is the function in question:

void bst_clear(struct TreeNode *tree_node) {
    //Clears all nodes recursively
    if (tree_node->left != NULL) {
        bst_clear(tree_node->left);
    }
    if (tree_node->right != NULL) {
            bst_clear(tree_node->right);
    }

    tree_node->key = NULL;
    tree_node->book = NULL;

    free((void*) tree_node);
    return;
}

Funny thing is, this does only happen while using a Linux OS (Mint 17.1) - both in a VM and as a dual-boot system. My main OS, which is Windows 7 64-bit, does compile and run without any issues and gets through the process entirely.

I am not sure whether something is actually wrong with the code (which could definitely be the case, I'm still a newbie) or whether my OS did mess something up there. But since this happened both in a VM and an actual system, it probably has nothing to do with missing system libraries (I guess).

So, does anyone have a clue on what's going on here?

EDIT: valgrind output:

==2946== Invalid free() / delete / delete[] / realloc()
==2946==    at 0x4C2BDEC: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==2946==    by 0x4008D3: bst_clear (booktree.c:84)
==2946==    by 0x400884: bst_clear (booktree.c:73)
==2946==    by 0x400884: bst_clear (booktree.c:73)
==2946==    by 0x400D17: main (main.c:66)
==2946==  Address 0xfff000030 is on thread 1's stack
==2946== 
==2946== Invalid free() / delete / delete[] / realloc()
==2946==    at 0x4C2BDEC: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)

...

==2946== 
==2946== 
==2946== HEAP SUMMARY:
==2946==     in use at exit: 128 bytes in 4 blocks
==2946==   total heap usage: 10 allocs, 10 frees, 280 bytes allocated
==2946== 
==2946== LEAK SUMMARY:
==2946==    definitely lost: 128 bytes in 4 blocks
==2946==    indirectly lost: 0 bytes in 0 blocks
==2946==      possibly lost: 0 bytes in 0 blocks
==2946==    still reachable: 0 bytes in 0 blocks
==2946==         suppressed: 0 bytes in 0 blocks
==2946== Rerun with --leak-check=full to see details of leaked memory

The error appeared multiple times - the line in question is the free() command - line 73 is just the recursive function call.

Now, if I got this right, I'm trying to free an object in the stack - read-only memory, right? The only thing I can think of are the struct declarations, which contain possibly static elements?

I'd also like to point out, that there is ZERO issue when running this on a Windows machine - does anyone know the reason for this?

EDIT 2:

This is how nodes are created:

char* root_author;
char* root_title;
root_author = "A B C\0";
root_title = "ABC\0";
struct TreeNode *root;
root = new_tree_node(579610, root_author, root_title);

char* n1a;
char* n1t;
n1a = "B C D";
n1t = "BCD";
struct TreeNode *n1 = new_tree_node(406759, n1a, n1t);
bst_insert(root, n1);

And this is the insert() function:

   void bst_insert(struct TreeNode *tree_node, struct TreeNode *new_node) {
    if (new_node->key < tree_node->key) {
        //If the key is smaller -> insert left
        if (tree_node->left == NULL) {
            //There is no left node yet
            tree_node->left = new_node;
            return;
        } else
            bst_insert(tree_node->left, new_node); //There is a node -> pass it on
    }

    else {
        //The key is larger -> right
        if (tree_node->right == NULL) {
            //There is no left node yet
            `enter code here`tree_node->right = new_node;
                return;
            } else
                bst_insert(tree_node->right, new_node); //There is a node -> pass it on
        }
    }