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

#define SIZE 26
struct TrieNode
{
	struct TrieNode *idx[SIZE];
	char str[50];
};
typedef struct TrieNode TRNODE;
/*------ CREATE A NEW TRNODE ------------*/
TRNODE* createTrNode()
{
	int n; TRNODE* p;
	p = (TRNODE*)malloc(sizeof(TRNODE));
	for (n = 0; n < SIZE; n++) p->idx[n] = NULL;
	p->str[0] = '\0';
	return p;
}
/*---- ADD A NODE IN THE TRIE ----*/
void insertWord(TRNODE *root,  char *word,  char *translation)
{
	TRNODE* p=root; int i;
	 char* letter=word;
	while (*letter)
	{
		i = *letter - 'a';
		if (p->idx[i] == NULL) p->idx[i] = createTrNode();
		p = p->idx[i];
		letter++;
	}
	//strcpy_s(p->str,translation);
	sprintf(p->str,"%s:%s",word,translation);
}
/*---- SEARCH FOR A WORD IN TRIE ----*/
TRNODE* search(TRNODE* root,  char* word)
{
	TRNODE* p = root; int i;
	while(*word)
	{
		i = *word - 'a';
		if (p->idx[i] == NULL) return NULL;
		p = p->idx[i];
		word++;
	}
	return p;
	//if (p->str[0] == '\0') return p;//NULL;
	//else return p;
}
/*---- PRINT THE TRIE ----*/
void printTrie(TRNODE *p)
{
	int i,j;
	if (p->str[0] != '\0')
		printf("%s\n",p->str );
	for (i = 0; i < SIZE; i++)
		if (p->idx[i] != NULL)	printTrie(p->idx[i]); 
}
/*----------------------------*/
void main()
{
	TRNODE *root= createTrNode();
	char word[50], translation[50];

	insertWord(root, "cat","gata, galn");
	insertWord(root, "dog","skylos");
	insertWord(root, "catch","pianw");
	insertWord(root, "all", "oloi");
	insertWord(root, "allternative", "enalaktikos");
	insertWord(root, "category", "katngoria");
	insertWord(root, "class", "klasn, taxn");
	insertWord(root, "book", "biblio");
	insertWord(root, "booking", "eggrafn");
	insertWord(root, "borrow", "daneizomai");
	insertWord(root, "dor", "porta, thyra");
		
	printf("\n%s\n", search(root, "cat")->str);
	printf("\n%s\n", search(root, "catch")->str);
	printf("\n%s\n", search(root, "dog")->str);

	printf("\nPRINT TREE\n");
	printTrie(root);
	
	printf("\nPRINT SUBTREE\n");
	printTrie(search(root, "cat"));
	printf("\n\n");
}