#include <stdio.h>
#include <stdlib.h>
//#include <conio.h>
#include <string.h>
#include "tree_stack_ops.h"

#define newline printf("\n")

struct edge
{
	int name;
    int lson;
    int rson;
};
typedef struct edge Edge;

void CREATE(BinaryTreeNode **);
void POSTORDER (BinaryTreeNode *);
void PREORDER(BinaryTreeNode *);
void INORDER (BinaryTreeNode *);
void POSTORDER_REC (BinaryTreeNode *);
void PREORDER_REC (BinaryTreeNode *);
void INORDER_REC (BinaryTreeNode *);
void VISIT (BinaryTreeNode *);
void FREE_TREE (BinaryTreeNode *);

BinaryTreeNode *create_node(BinaryTreeDataType);

int main()
{
    BinaryTreeNode *T;
    CREATE(&T);

    INORDER_REC(T);
    newline;


    FREE_TREE(T);
    return 0;
}

BinaryTreeNode *create_node(BinaryTreeDataType data)
{
    BinaryTreeNode *temp = (BinaryTreeNode *) malloc(sizeof(BinaryTreeNode));

    if (temp == NULL) fprintf(stderr, "Error in memory allocation.\n");
    else
    {
        temp->DATA = data;
        temp->LSON = NULL;
        temp->RSON = NULL;
    }

    return temp;
}

int read_tree_input (Edge **edges)
{
	int i, n;
    int lson, rson;

	scanf("%d\n", &n);
    *edges = (Edge *) malloc (n*sizeof(Edge));
    for (i = 0; i < n; i++)
    {
        (*edges)[i].name = i+1;

        scanf("%d %d\n", &lson, &rson);
        (*edges)[i].lson = lson;
        (*edges)[i].rson = rson;

        // printf("%d %d %d\n", edges[i].name, edges[i].lson, edges[i].rson);
    }

	return n;
	//free(edges);
}

void CREATE (BinaryTreeNode **T)
{
	Edge *edges;
    BinaryTreeNode **nodes;
	int n;
	int i = 0;

	n = read_tree_input(&edges);

    nodes = (BinaryTreeNode **) malloc (n*sizeof(BinaryTreeNode*));
	for (i = 0; i < n; i++)
    {
        nodes[i] = (BinaryTreeNode *) malloc (sizeof(BinaryTreeNode));
        nodes[i]->DATA = edges[i].name;
        nodes[i]->LSON = NULL;
        nodes[i]->RSON = NULL;
    }

    // printf("okay\n");
    for (i = 0; i < n; i++)
    {
        // printf("%d %d %d\n", edges[i].name, edges[i].lson, edges[i].rson);

        if (edges[i].lson > 0) nodes[i]->LSON = nodes[edges[i].lson-1];
        if (edges[i].rson > 0) nodes[i]->RSON = nodes[edges[i].rson-1];

        // printf("Node %d :: ", nodes[i]->DATA);

        // if (nodes[i]->LSON == NULL) printf("LSON NULL :: ");
        // else printf("LSON %d :: ", nodes[i]->LSON->DATA);

        // if (nodes[i]->RSON == NULL) printf("RSON NULL\n");
        // else printf("RSON %d\n", nodes[i]->RSON->DATA);
    }

    *T = nodes[0];


	free(edges);
}

void POSTORDER(BinaryTreeNode *T)
{
    BinaryTreeNode *alpha; Stack S; StackElemType elem;
	InitStack(&S);
    alpha = T;

    A:
    while (alpha != NULL)
    {
        elem.address = alpha;
        elem.tag = '-';
        PUSH (&S, elem);
        alpha = alpha ->LSON;
    }

    B:
    if (IsEmptyStack(&S)) return;
    else
    {
        POP(&S, &elem);
        alpha = elem.address;
        if (elem.tag == '-')
        {
            elem.tag = '+';
            PUSH(&S, elem);
            alpha = alpha->RSON;
            goto A;
        }
        else
        {
            VISIT(alpha);
            goto B;
        }
    }

    return;
}

void PREORDER(BinaryTreeNode *T)
{
    BinaryTreeNode *alpha; Stack S; StackElemType elem;
	InitStack(&S);
    alpha = T;

    while (alpha != NULL)
    {
	    while (alpha != NULL)
	    {
	    	VISIT(alpha);
	        elem.address = alpha;
	        PUSH (&S, elem);
	        alpha = alpha ->LSON;
	    }
		while (alpha == NULL)
		{
			if (IsEmptyStack(&S)) return;
			POP(&S, &elem);
	   		alpha=elem.address->RSON;
		}
	}
    return;
}

void INORDER(BinaryTreeNode *T)
{
    BinaryTreeNode *alpha; Stack S; StackElemType elem;
	InitStack(&S);
    alpha = T;

    while (alpha != NULL)
    {
	    while (alpha != NULL)
	    {
	        elem.address = alpha;
	        PUSH (&S, elem);
	        alpha = alpha ->LSON;
	    }
		while (alpha == NULL)
		{
			if (IsEmptyStack(&S)) return;
			POP(&S, &elem);
			VISIT(elem.address);
	   		alpha=elem.address->RSON;
		}
	}
    return;
}

void PREORDER_REC(BinaryTreeNode *T)
{
	BinaryTreeNode *alpha;
	alpha=T;
	VISIT(alpha);
	if(alpha->LSON!=NULL)PREORDER_REC(alpha->LSON);
	if(alpha->RSON!=NULL)PREORDER_REC(alpha->RSON);
}

void INORDER_REC(BinaryTreeNode *T)
{
	BinaryTreeNode *alpha;
	alpha=T;
	if(alpha->LSON!=NULL)PREORDER_REC(alpha->LSON);
	VISIT(alpha);
	if(alpha->RSON!=NULL)PREORDER_REC(alpha->RSON);
}

void VISIT(BinaryTreeNode *T)
{
    printf("-%d-", T->DATA);
}

/**
Deallocating a Binary Tree should be
done in POSTORDER. Suggested is iterative
to avoid stack overflow.
**/
void FREE_TREE (BinaryTreeNode *T)
{
    if (T != NULL)
    {
        FREE_TREE(T->LSON);
        FREE_TREE(T->RSON);
        free(T);
    }

}