Listing 1 Minimal binary tree program.

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

/*  Tree Node Definition */

typedef struct node {
   struct node *left;
   struct node *right;
   char key;
}node;

/*  Recursive Minimal Tree Insertion Function */

node *tree_insert(node *root, node *new_node)
{
   if(! root) {
   root = (node *) calloc(1, sizeof(node));
   root->key = new_node->key;
   return root;    /* return pointer to new memory block */
   }
   if(new_node->key == root->key)      /* if ==, return */
   return root;
   else if(new_node->key < root->key)  /* if <, go left */
   root->left = tree_insert(root->left, new_node);
   else                                /* else go right */
      root->right = tree_insert(root->right, new_node);

   return root;
}

/* Recursive Minimal Tree In-Order Traversal Function */

void tree_trace(node *root)
{
   if(! root)
   return;
   tree_trace(root->left);
   printf("\n%c", root->key);
   tree_trace(root->right);
}

/* Minimal Tree Test Driver */

void main(void)
{
   char c, m = 'm';
   node *tree_root = NULL;
   node this_node = { NULL, NULL, '\0' };

   this_node.key = m;
   tree_root = tree_insert (tree_root, &this_node);

   for(c = '\x1';c < '\x5';c++) {
      this_node.key = m + c;
   tree_insert(tree_root, &this_node);
      this_node.key = m - c;
   tree_insert(tree_root, &this_node);
   }
   tree_trace(tree_root);
   printf("\n");
   exit(0);                  /* minimal, so let exit()  */
                         /* free the dynamic memory */
}
/*  End of File */