Tree ADT implementation in C As a learning exercise, I decided to implement a BST and add functionality to it slowly. I'd appreciate any feedback.

I should also point out that I borrowed the template from the here.

tree.h header file 

typedef char treeElement;
typedef struct TreeNodeTag{
  treeElement  element;
  struct TreeNodeTag  *left, *right;
}treeNode;

typedef struct treeCDT{
  treeNode *root;
}treeCDT;

typedef struct treeCDT *treeADT;

treeNode* addTreeHelper(treeNode**, treeElement);
void addTree(treeADT, treeElement);
int destroyTree(treeADT);
int destroyTreeHelper(treeNode*);
void createTree(treeADT*);
void printTree(treeADT);
void printTreeHelper(treeNode*);


Implementation tree.c

treeNode* addTreeHelper(treeNode **root, treeElement element){

  if(!*root){
    treeNode *temp;
    temp = malloc(sizeof(treeNode));
    temp-&gt;element = element;
    temp-&gt;left = NULL;
    temp-&gt;right = NULL;

    /*
    *root =  malloc(sizeof(treeNode));
    (*root)-&gt;element = element;
    (*root)-&gt;left = NULL;
    (*root)-&gt;right = NULL;
    */
    *root = temp;
    return *root;
  }

  if( (*root)-&gt;element &gt;= element ){
    addTreeHelper( &amp;(*root)-&gt;left, element);
  }
  else{
    addTreeHelper(&amp;(*root)-&gt;right, element);
  }

  return *root;
}

void addTree(treeADT tree, treeElement element){
  addTreeHelper(&amp;(tree-&gt;root), element);
}

int destroyTree(treeADT tree){
  destroyTreeHelper(tree-&gt;root);
  free(tree);
  return 0;
}

int destroyTreeHelper(treeNode* root){
  if(root){
    destroyTreeHelper(root-&gt;left);
    destroyTreeHelper(root-&gt;right);
    free(root);
  }
  return 0;
}

void createTree(treeADT* tree){
  *tree = malloc(sizeof(treeCDT));
  if(!*tree){
    fprintf(stderr, "Problem allocating tree");
  }
}

void printTree(treeADT tree){
  printTreeHelper(tree-&gt;root);  
}


void printTreeHelper(treeNode * node){
  if(node){
    printf("%c\n", node-&gt;element);
    if(node-&gt;left)
      printTreeHelper(node-&gt;left);
    if(node-&gt;right)
      printTreeHelper(node-&gt;right);
  }  
}
API Changes

Currently, as a user of your tree, I have to figure out whether or not I need to call addTree, destroyTree, printTree or their corresponding helper functions. These helper functions are implementation details of the tree and they should not be exposed to the user. Ditto with the treeNode struct. Moreover, if you will be dynamically allocating your tree, you should just be doing so inside the createTree function and then returning that pointer back to the user. I also don't see a need for the typedef to a struct treeCDT *. I personally prefer knowing what the exact type I'm dealing with here and treeADT really doesn't tell me anything. Your header file really should be this:

BST.h

typedef char treeElement;
struct treeCDT;

void addTree(struct treeCDT *, treeElement);
void destroyTree(struct treeCDT *);
struct treeCDT *createTree();
void printTree(struct treeCDT *);


Then, in your implementation file, you can implement all your helpers and mark them as static; this way, your user cannot call them from outside code. You can now define your treeNode and treeCT struct here as well:

BST.c

typedef struct TreeNodeTag{
    treeElement  element;
    struct TreeNodeTag  *left, *right;
} treeNode;

typedef struct treeCDT {
    // ...
} treeADT;

static void addTreeHelper(treeNode**, treeElement)
{

}

static void destroyTreeHelper(treeNode*)
{

}

static void printTreeHelper(treeNode*)
{

}


Bug

You have an error that can cause undefined behavior in your create tree function:

void createTree(treeADT* tree){
  *tree = malloc(sizeof(treeCDT)); // error here.
  if(!*tree){
    fprintf(stderr, "Problem allocating tree");
  }
}


Remember that malloc returns a pointer to memory without initializing it; in other words, the values could be anything! Therefore, the value in the root member of your treeADT is not initialized to NULL like it should be. (See below for alternate implementation).

Factor your code out

As it is now, your implementation is pretty limited as there are no searching, removing, or other utility functions. You can imagine that there will be a need to constantly create new tree nodes. I would make that a function (and mark it static).

static treeNode *createTreeNode(treeElement elem)
{
    treeNode *node = calloc(1, sizeof(*node));
    if (node){
        node-&gt;element = elem;
    }
    return node;
}


Now your tree creation function can be:

struct treeCDT *createTree()
{
    return calloc(1, sizeof(struct treeCDT));
}


and the insertion function is trivial now:

void addTree(struct treeCDT *tree, treeElement elem)
{
     if (!tree) { return; }

     if (!(tree-&gt;root)) {
         tree-&gt;root = createTreeNode(elem);
     } else {
         struct treeCDT *copy = tree-&gt;root;
         int inserted = 0;

         while (!inserted) {
             if (elem &lt; copy-&gt;element) {
                 if (copy-&gt;left)
                     copy = copy-&gt;left;
                 else {
                     copy-&gt;left = createTreeNode(elem);
                     inserted = 1;
                 }
             } else if (elem &gt; copy-&gt;element) {
                 if (copy-&gt;right)
                     copy = copy-&gt;right;
                 else {
                     copy-&gt;right = createTreeNode(elem);
                     inserted = 1;
                 }
             } else {
                 inserted = 1;
             }
         }
     }
}