#include<stdio.h>
#include<stdlib.h>
#define MAXCHILD 4
#define MAXNODE 20


struct treenode
{
    char info;
	// pointer to first child
	struct treenode *firstchild;
	// pointer to next sibling or father node
	struct treenode *next;
	// flag=0 if next is sibling , 1 if next is father node
	int flag;
};

typedef struct treenode *NODEPTR;
int nodename=65;// used for naming tree node
int nodecount=0; // To count total number of node in Tree
// To store address of ptr to every node
// Every Node and its related info can be directly accessed from it
NODEPTR *stack; 
NODEPTR root;//Pointer to the root of the Tree
	
/*  All function written are listed Here */
NODEPTR getnode();
void freenode(NODEPTR p);
NODEPTR maketree(char x);
void setchild(NODEPTR tptr,char child[],int n);
void breadthTraversalTreeGenerate();

int main()
{
	int i;
	srand(time(NULL));// used to get random Trees
	// Random Tree Generation
	stack = malloc(sizeof(*stack)*20);
	breadthTraversalTreeGenerate();
	free(stack);
	
	
	
	printf("\n");
	return 0;
}

NODEPTR getnode()
{
	NODEPTR p;
	p=(struct treenode*)malloc(sizeof(struct treenode));
	return p;
}

void freenode(NODEPTR p)
{
	free(p);
}

NODEPTR maketree(char x)
{
	NODEPTR p;
	p=getnode();
	p->info=x;
	p->flag=0;
	p->firstchild=NULL;
	p->next=NULL;
	
	
	return(p);
}

void setchild(NODEPTR tptr,char child[],int n)
{
	NODEPTR p,q;
	int i,j=0;
	if((tptr->firstchild)!=NULL)
		printf("VOID INSERTION");
	else 
	{
		if (n==1)
			printf("\n%c has one child, namely \t",tptr->info);
		else
			printf("\n%c has %d children, namely \t",tptr->info,n); 
		
		p=maketree(child[j]);
		j++;
		tptr->firstchild=p;
		printf("%c",tptr->firstchild->info);
		stack[nodecount]=&(tptr->firstchild);
    	nodecount++;
		for(i=0;i<n-1;i++)
		{
			q=maketree(child[j]);
			j++;
			p->next=q;
			printf("\t%c",q->info);
			stack[nodecount]=&(p->next);
    		nodecount++;
			p=q;
		}
		p->flag=1;
		p->next=tptr;
		printf("\n");
	}
}
	
void breadthTraversalTreeGenerate()
{
	int i,j,n,dummy;
	char *child,lol;
	NODEPTR tptr;
	
	// tree-> info can be given anything I used char notation,it will
	// be easy to understand order traversing using alphabats.
	root=maketree(nodename);
	// to store address of ptr to everynode
	// will be used in generating children
	stack[nodecount]=&root;
    nodecount++;
	// nodename++ will make next nodename as next character
	//i.e A, then B, then C & so on..
	nodename++;

	
	// Set children for next levels
	dummy=nodecount-1;
	while(dummy>=0)
	{	
		dummy=nodecount-1;
		tptr=*(stack[dummy]);
		while(tptr->firstchild==NULL)
		{
			
			n=(rand()%(MAXCHILD))+1;
			if(nodecount+n>MAXNODE)
				break;
			child=(char *)malloc(sizeof(char)*n);
			for(i=0;i<n;i++)
			{
				child[i]=nodename;
				nodename++;
			}
			setchild(tptr,child,n);
			dummy--;
			if (dummy<0)
			{
				dummy++;
				break;
			}
			tptr=*stack[dummy];
		
		}
		if(nodecount+n>MAXNODE)
			break;
	}
	
}