Consider a forest represented in the form of a linked list where each node points to a Binary Search Tree of words of length $$\texttt{L}$$. The list is sorted according to the length of the word.

Example: After the insertion of the following words in this order: $$\texttt{d}$$, $$\texttt{xde}$$, $$\texttt{mir}$$, $$\texttt{b}$$, $$\texttt{m}$$, $$\texttt{dfgy}$$, $$\texttt{xxyz}$$, $$\texttt{h}$$, $$\texttt{miz}$$, $$\texttt{dfaa}$$, $$\texttt{def}$$, $$\texttt{mirt}$$, $$\texttt{ghte}$$; we obtain the following forest:

• Insert the following words into the above forest: $$\texttt{be}$$, $$\texttt{behave}$$ and $$\texttt{been}$$.
• Give all the declarations needed to implement the above forest.
• Write a function that searches for a word $$\texttt{W}$$ in the forest and inserts it if it's not found.
• Write a function that prints all the words of the forest that begin with a character $$\texttt{C}$$ without traversing all the node of the trees of the forest.

typedef struct nodeF  {
	int length;
	struct node *tree;
	struct nodeF *next;
} *forest;


forest CreateForest()
{
	forest f;
	f=NULL;
	return f;
}

void insert(forest *f, element str)
{
	forest f1=*f;
	forest B=NULL, temp;
	Btree Btemp, BT,BS,BR;
	int found=0, stop=0;

	while(f1!=NULL && !found && !stop)
	{
		if(f1->length==strlen(str))
			found=1;
		else
			if(f1->length > strlen(str))
				stop=1;
			else
			{
				B=f1;
				f1=f1->next;
			}
	}
	

	if(!found)
	{

		Btemp = (Btree) malloc(sizeof(struct node));
		strcpy(Btemp->data,str);
		Btemp->left=Btemp->right=NULL;


		temp = (forest) malloc(sizeof(struct nodeF));
		temp->length=strlen(str);
		temp->tree=Btemp;
		
		if(B!=NULL)
		{
			temp->next=B->next;
			B->next=temp;
		}
		else
		{
			temp->next=NULL;
			*f=temp;
		}
		
	}
	else
	{
		//search in the BST
		BT=f1->tree;
		found=0;
		while(BT!=NULL && !found)
		{
			if(!strcmp(BT->data,str))
				found=1;
			else
			{
				BS=BT;
				if(strcmp(BT->data,str)>0)
					BT=BT->left;
				else
					BT=BT->right;
			}
		}
	
			
		BR = (Btree) malloc(sizeof(struct node));
		strcpy(BR->data,str);
		BR->left=BR->right=NULL;

		if(strcmp(str,BS->data)<0)
			BS->left=BR;
		else
			BS->right=BR;
	}
	

}

void printBtree(Btree B)
{
	if(B)
	{
		printBtree(B->left);
		printf(" - - - - %s\n",B->data);
		printBtree(B->right);
	}
}
 

void print(forest f)
{ 
	while(f)
	{
		printf("%d \n",f->length);
		printBtree(f->tree);
		f=f->next;
	}
}
 

int searches(Btree A, char C, Btree *B)
{
	Btree temp=A;
	int found=0;
	while(temp)
	{
		if(temp->data[0]==C)
		{
			found=1;
			*B=temp;
		}
		if(temp->data[0]>C)
			temp=temp->left;
		else
			temp=temp->right;
	}
	return found;
}

void fillthestack(stack *s, Btree temp, char C)
{

	if(temp)
	{
		if((temp->data)[0]==C)
		{
			Push(s,temp);
			fillthestack(s,temp->left, C);
			fillthestack(s,temp->right, C);
		}
		else
			if((temp->data)[0]>C)
				fillthestack(s,temp->left, C);
			else
				fillthestack(s,temp->right, C);
	}
}

void print_following(Btree A, char C)
{
	stack s;
	Btree temp=A;
	int possible;
	s=CreateStack();

	fillthestack(&s, temp, C);

	if(!isEmptyStack(s))
	{
		Top(s,&temp);
		Pop(&s);
		printf("\nWord %s",temp->data);
		temp=temp->right;
		possible=1;
		while(possible)
		{
			while(temp)
			{
				Push(&s,temp);
				temp=temp->left;
			}
			if(!isEmptyStack(s))
			{
				Top(s,&temp);
				Pop(&s);
				if((temp->data)[0]==C)
					printf("\nWord %s",temp->data);
				temp=temp->right;	
			}
			else
			{
				possible=0;
			}
		}
	}
}

void print_forest(forest f, char C)
{
	forest Q=f;
	int found;
	Btree B;
	printf("\n\nAll words beginning with letter %c",C);
	while(Q)
	{
	
		printf("\n\nTree of length %d",Q->length);
		found=searches(Q->tree,  C, &B);
		if(found)
		{
			//printf("\nSmallest word beginning with %c: %s",C,B->data);
			print_following(B,C);
		}
		Q=Q->next;
	}
}