#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
char *StrToLower(char *s);


struct node{
char *word;
struct node *left;
struct node *right;
};

typedef struct node NODE;
void display( NODE *);
NODE *search(char *z);
NODE *k(char *y);
NODE * root = NULL;



int main (void){
k("lzzzzz");
k("ezzzzz");
k("pzzzzz");
k("");
k("");
k("");
k("");
k("");
k("");
k("");
k("");
k("");
k("");
k("");
k("");
k("");
k("");
k("");
k("");
k("");
k("");
k("");
k("");
k("");
k("");
k("");
k("");
k("");
k("");
k("");
k("");
k("");
k("");
k("");
k("");
k("");
k("");
k("");
k("");
k("");
k("");
k("");
k("");
k("");
k("");
k("");


display(root);


printf("\n");
printf("*********************\n");
printf("\n");


search("the");
search("when");

return 0;}

/* displaying of all NODEs */
void display(NODE * q){
if(q == NULL)return ;
display(q->left);
printf("%s\n",q->word);
display(q->right);}




/* generation of kouzoutai */
NODE *k(char *y){
NODE *new;

NODE **pp;
char work[50];
pp = &root;
strcpy(work,y);
StrToLower(work);

while(*pp != NULL){
 if(strcmp(work , (*pp)->word) == 0)return NULL;
 else if (strcmp(work ,(*pp)->word) < 0)pp = &(*pp)->left;
 else pp = &(*pp)->right;
}
new = (NODE *)malloc(sizeof(NODE)) ;
if(new == NULL)exit(1);
new->left = NULL;
new->right = NULL;
new->word = (char *)malloc(strlen(work)  + 1);
strcpy(new->word , work);
*pp = new;
return new;
}
/* searching of string */
NODE *search(char *z){
NODE *p;
p = root;
while(p!= NULL){
if(strcmp(z,p->word) == 0){
 printf("atari=%s\n",z);
 return;}
else if (strcmp(z, p->word) < 0)
 p = p->left;
else 
 p = p->right;
}
printf("hazure=%s\n",z);
return NULL;
}
/* UpperCase to LowerCase */
char *StrToLower(char *s){
char *p;
for(p = s;*p;p++)
*p = tolower(*p);
return (s);
}