#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct node
{
     char data;
     char array[11];
     struct node* left;
     struct node* right;
}binTreeNode;

typedef struct item
{
	struct node* treeNode;
	struct item *next;
}Q_ITEM;

void push(Q_ITEM **start, struct node* input)
{
      Q_ITEM *temp = (Q_ITEM*) malloc(sizeof(Q_ITEM));
			temp->treeNode = input;


			if ((*start) == NULL)
			{
				temp->next = temp;
        			(*start) = temp;
			}
			else
			{
				temp->next = (*start)->next;
				(*start)->next = temp;
	      			(*start)= temp;
			}
}

int isEmpty( Q_ITEM ** start)
{
   if ((*start) == NULL)
     return 1;
   else
     return 0;
}
struct node* pop(Q_ITEM ** start)
{
      struct node* temp;
      temp = (*start)->treeNode;


    if( ((*start)->next) == NULL)
		{

       (*start) = NULL;
        return(temp);
		}
		else
		{
   Q_ITEM* temp2 = (*start)->next;
	     (*start)->next = temp2->next;
            if ((*start)==temp2)
                        {
			                      (*start)=NULL;
                        }
           return(temp);

		}

}
void printInorder(struct node** root, Q_ITEM** pointerTotopOfStack)
{
int done=0;
  struct node * TrvPtr = (*root);
  while(!done)
  {
    while(TrvPtr != NULL)
    {
       if(TrvPtr -> left != NULL)
       {
       push(pointerTotopOfStack, TrvPtr);
       TrvPtr = TrvPtr -> left;
       }
       else
       {
         printf("%c", TrvPtr -> data);
         TrvPtr = TrvPtr -> right;
       }
    }
        if( isEmpty(pointerTotopOfStack) == 1)
        {
          done = 1;
        }
        else
        {
        TrvPtr = pop(pointerTotopOfStack);
        printf("%c", TrvPtr -> data);
        TrvPtr = TrvPtr -> right;
        }

  }
}
void printPreorder(struct node** root, Q_ITEM** pointerTotopOfStack)
{
  int done=0;
  struct node * TrvPtr = (*root);
  while(!done)
  {
    while(TrvPtr != NULL)
    {
       printf("%c", TrvPtr -> data);

       if(TrvPtr -> left != NULL)
       {
       push(pointerTotopOfStack, TrvPtr);

       TrvPtr = TrvPtr -> left;

       }
       else
       {
         TrvPtr = TrvPtr -> right;

       }
    }
        if( isEmpty(pointerTotopOfStack)==1)
        {
          done = 1;

        }
        else
        {
        TrvPtr = pop(pointerTotopOfStack);

        TrvPtr = TrvPtr -> right;
        }

  }
}
void printInorder2(struct node* node)
{
     if (node == NULL)
          return;

     printInorder2(node->left);

     printf("%c", node->data);

     printInorder2(node->right);
}


void printPreorder2(struct node* node)
{
     if (node == NULL)
          return;

     printf("%c", node->data);

     printPreorder2(node->left);

     printPreorder2(node->right);
}
struct node* insert(struct node *root, char letter, char *array)
{
    struct node * SavedRoot = root;
   if(root == NULL)
   {
     struct node* node = (struct node*) malloc(sizeof(struct node));
     strcpy(node -> array, array);
     node->data = letter;
     node->left = NULL;
     node->right = NULL;
     return(node);
   }
   else if(root->data < letter) // if the new letter is greater than, gets put on right side
   {
      root = insert(root -> right, letter, array);
      SavedRoot -> right = root;
      //printf("\n just set right child of %c to %c\n", SavedRoot->data, root->data);
        return(SavedRoot);
   }
   else
   {
     root = insert(root -> left, letter, array);
     SavedRoot -> left = root;
     //printf("\n just set left child of %c to %c\n", SavedRoot->data, root->data);
     return(SavedRoot);
   }


}
// Find function
void find(struct node * root, char letter)
{
  if(root==NULL)
  {
    printf("Not found");
    return;
  }
  else if( root -> data == letter)
  {
      printf("Found the string \"%s\" there", root -> array);
  }
  else if( root ->data < letter)
  {
    find(root -> right, letter);
  }
  else
  {
    find(root -> left, letter);
  }

}

int main()
{

char input;
char unUsed;
char letter;
char array[11];

printf("\nEnter choice (lower case is also acceptable) --- (I)nsert, (F)ind, (Q)uit: \n");
scanf("%c", &input);
scanf("%c", &unUsed);

struct node* root = NULL;
Q_ITEM* topOfStack =NULL;

while(input != 'Q' && input != 'q')
{
 if(input == 'I' || input == 'i')
   {
      printf("\nEnter a node\n");
      scanf("%c", &letter);
      scanf("%c", &unUsed);

      printf("\n Enter a string of up to 10 characters for %c's data: ", letter);
      scanf("%s", array);
      scanf("%c", &unUsed);

      root = insert(root, letter, array);
      printf("Preorder traversal is: ");
      printPreorder(&root,&topOfStack );
      printf("\nRecursive PreOrder: ");
      printPreorder2(root);
      printf("\n");
      printf("\nInorder traversal is: ");
      printInorder(&root, &topOfStack);
      printf("\nRecursive inOrder: ");
      printInorder2(root);


   }
   else
   {
      printf("\nEnter a node\n");
      scanf("%c", &letter);
      scanf("%c", &unUsed);
      find(root, letter);
   }
printf("\nEnter choice (lower case is also acceptable) --- (I)nsert, (F)ind, (Q)uit: \n");
scanf("%c", &input);
scanf("%c", &unUsed);
}
}