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

#define NINS 25
#define DNL 1
#define DNR 2
#define UPL 3
#define UPR 4

typedef struct _treenode {
   int key;
   struct _treenode *L, *R;
} treenode;
typedef treenode *BST;

/* Standard BST insertion function */
BST insert ( BST T, int a )
{
   treenode *p, *q;

   p = T; q = NULL;
   while (p != NULL) {
      if (a == p -> key) return T;             /* Don't insert duplicate keys */
      q = p;
      if (a < p -> key) p = p -> L; else p = p -> R;     /* Move down further */
   }
   p = (treenode *)malloc(sizeof(treenode));
   p -> L = p -> R = NULL;
   p -> key = a;
   if (q == NULL) return p;                     /* Insertion in an empty tree */
   if (a < q -> key) q -> L = p; else q -> R = p;
   return T;
}

/* This is the constant-space in-order traversal function */
void printBST ( BST T )
{
   treenode *p, *q, *r;
   int nextmove, firstprint;

   /* First, print an empty tree */
   printf("T = ");
   if (T == NULL) {
      printf("()\n");
      return;
   }

   /* Next, consider the case of a non-empty tree */
   p = T;                                 /* The traversal starts at the root */
   q = NULL;                                /* The parent of the root in NULL */
   nextmove = DNL;   /* At any newly visited node, we first explore down-left */
   firstprint = 1;   /* Needed only for pretty printing -- fancy feature only */

   /* The following loop implements the traversal */
   while (1) {
      if (nextmove == DNL) {          /* Next scheduled movement is down-left */
         if (p -> L != NULL) {            /* It is posssible to make the move */
            /* Go one level down the tree */
            r = p -> L; p -> L = q; q = p; p = r;
         } else {                      /* It is not possible to make the move */
            /* Print the key value at p */
            printf("%c%d", (firstprint) ? '(' : ',', p -> key);
            firstprint = 0;
            /* Schedule the next movement to down-right for next iteration */
            nextmove = DNR;
         }
      } else if (nextmove == DNR) {  /* Next scheduled movement is down-right */
         if (p -> R != NULL) {             /* It is possible to make the move */
            /* Go one level down the tree */
            r = p -> R; p -> R = q; q = p; p = r;
            /* Schedule the next movement to down-left for next iteration */
            nextmove = DNL;
         } else {                      /* It is not possible to make the move */
            /* Schedule the correct upward movement for the next iteration */
            if (q == NULL) break;         /* Case of root with no right child */
            else nextmove = (p -> key < q -> key) ? UPL : UPR;
         }
      } else if (nextmove == UPL) {     /* Next scheduled movement is up-left */
         /* Carry out the upward movement */
         r = q -> L; q -> L = p; p = q; q = r;
         /* We are done with the left subtree, so print the key */
         printf("%c%d", (firstprint) ? '(' : ',', p -> key);
         firstprint = 0;
         /* Explore the right subtree */
         nextmove = DNR;
      } else if (nextmove == UPR) {    /* Next scheduled movement is up-right */
         /* Carry out the upward movement */
         r = q -> R; q -> R = p; p = q; q = r;
         /* Schedule the correct upward movement for the next iteration */
         if (q == NULL) break;   /* Right subtree of root printed - terminate */
         else nextmove = (p -> key < q -> key) ? UPL : UPR;
      }
   }
   printf(")\n");
}

/* Standard recursive freeing of a BST */
BST freeBST ( BST T )
{
   if (T != NULL) {
      freeBST(T -> L); freeBST(T -> R); free(T);
   }
   return NULL;
}

int main ()
{
   int i, a;
   BST T;

   srand((unsigned int)time(NULL));
   printf("Initializing the tree\n");
   T = NULL;
   printBST(T);
   for (i=0; i<NINS; ++i) {
      a = 1 + rand() % 99;
      printf("Inserting %d\n", a);
      T = insert(T,a);
      printBST(T);
   }
   printf("Freeing the tree\n");
   T = freeBST(T);
   printBST(T);
   exit(0);
}