C program: Binary tree

Question

I need some help with creating a binary tree program. Basically, I have different methods for creating and using a binary tree table (insert, find etc). The methods are called from other classes. Right now I don't think my insert function is working properly since when I print the table out it only shows the last node of the tree.

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#define __USE_BSD
#include <string.h>

#include "speller.h"
#include "dict.h"

typedef struct node *tree_ptr;
struct node {
    Key_Type element; // only data is the key itself
    tree_ptr left, right;
    // add anything else that you need
};

struct table {
    tree_ptr head; // points to the head of the tree
    // add anything else that you need
};

Table initialize_table(/*ignore parameter*/) {
    Table newTable = malloc(sizeof(Table));
    newTable->head = NULL;
    return newTable;
}

void insert_again(Key_Type key, tree_ptr node) {
    Key_Type currentKey = node->element;
    //printf("%s\n%s", currentKey, key);
    int keyCompare = strcmp(key, currentKey);
    // Move to the left node.
    if (keyCompare < 0) {
        //printf("%s\n%s", currentKey, key);
        // If left node is empty, create a new node.
        if (node->left == NULL) {
            tree_ptr newPtr = malloc(sizeof(tree_ptr));
            newPtr->element = key;
            newPtr->left = NULL;
            newPtr->right = NULL;
            node->left = newPtr;
        } else {
            insert_again(key, node->left);
        }
    }
    // Move to the right node.
    else if (keyCompare > 0) {
        //printf("%s\n%s", currentKey, key);
        // If right node is empty, create a new node.
        if (node->right == NULL) {
            tree_ptr newPtr = malloc(sizeof(tree_ptr));
            newPtr->element = key;
            newPtr->left = NULL;
            newPtr->right = NULL;
            node->right = newPtr;
        } else {
            insert_again(key, node->right);
        }
    }
}

Table insert(Key_Type key, Table table) {
    // if it's a new tree.
    if (table->head == NULL) {
        tree_ptr headPtr = malloc(sizeof(tree_ptr));
        headPtr->element = key;
        headPtr->left = NULL;
        headPtr->right = NULL;
        table->head = headPtr;
        //printf("%s", table->head->element);
    }
    // if the tree already exists
    else {
        //printf("%s", table->head->element);
        insert_again(key, table->head);
    }
    //printf("%s", table->head->element);
    return table;
}

Boolean find_key(Key_Type key, tree_ptr node) {
    Key_Type currentKey = node->element;
    int keyCompare = strcmp(key, currentKey);
    if (node != NULL) {
        if (keyCompare == 0) {
            return TRUE;
        } else
        if (keyCompare == -1) {
            return find_key(key, node->left);
        } else {
            return find_key(key, node->right);
        }
    } else {
        return FALSE;
    }
}

Boolean find(Key_Type key, Table table) {
    return find_key(key, table->head);
}

void print_tree(tree_ptr node) {
    if (node == NULL) {
        return;
    }
    print_tree(node->left);
    printf("%s\n", node->element);
    print_tree(node->right);
}

void print_table(Table table) {
    print_tree(table->head);
}

void print_stats(Table table) {
}

Answer 1

You have to search for an empty child node to insert a new node into a tree. Use a pointer to a pointer to notice the empty child node. Apart from this you have to allocate memory for sizeof(struct node)and not for sizeof(struct node*) as you did. In relation to the code I can see, that type of Key_Type is char*. So you have to use strcmp to compare keys and you have to allocate memory and to copy the key into the node.

Boolean insert( Key_Type key, Table table ) 
{
   tree_ptr *ppNode = &(table->head); // pointer to pointer to node (struct node **)
   while ( ppNode != NULL )
   {
      int keyCompare = strcmp( key, (*ppNode)->element );
      if ( keyCompare == 0 )
          return FALSE; // element with key is already member of tree

      if ( keyCompare < 0 )
          ppNode = &((*ppNode)->left);  // go to left child
      else 
          ppNode = &((*ppNode)->right); // go to right child
   }

   // now ppNode is either a pointer to an empty child pointer,
   // or to table->head if the tree is empty

   *ppNode = malloc( sizeof(struct node) ); // allocate new node right to target
   (*ppNode)->left = NULL;
   (*ppNode)->right = NULL;
   (*ppNode)->element = malloc( strlen(key) + 1 );
   strcpy( (*ppNode)->element, key );

   return TRUE; // new node added successfully
}

Finding a node with key is similar to find an empty child pointer:

Boolean find_key( Key_Type key, Table table ) 
{
   tree_ptr pNode = table->head;
   while ( ppNode != NULL )
   {
      int keyCompare = strcmp( key, pNode->element );
      if ( keyCompare == 0 )
          return TRUE; // element with key was found

      if ( keyCompare < 0 )
          pNode = pNode->left;  // go to left child
      else 
          pNode = pNode->right; // go to right child
   }
   return FALSE; // key is not member of tree
}