#include<stdio.h>
#include<stdlib.h>
#define LAMBDA NULL

typedef char labeltype;

typedef struct cell_tag{
  labeltype label;
  struct celltag *leftchild;
  struct celltag *rightchild;
}celltype;

typedef celltype *node;
typedef celltype *BinaryTree;

void BiCreate(labeltype l, BinaryTree TL, BinaryTree TR, BinaryTree *Tp){
  *Tp=(celltype*)malloc(sizeof(celltype));
  (*Tp)->label=l;
  (*Tp)->leftchild=TL;
  (*Tp)->rightchild=TR;
}

void BiMakeNull(BinaryTree *Tp){
  *Tp=NULL;
}

int BiEmpty(BinaryTree T){
  if(T==NULL) return 1;
  return 0;
}

void BiLeftSubtree(BinaryTree T, BinaryTree *TLp){
  if(BiEmpty(T))exit(8); //nije definirano
  (*TLp)=T->leftchild;
}

void BiRightSubtree(BinaryTree T, BinaryTree *TRp){
   if(BiEmpty(T))exit(8);
  (*TRp)=T->rightchild;
}

node BiInsertLeftChild(labeltype l, node i, BinaryTree *Tp){
  if(i==NULL) exit(8); //nije definirana
  if(i->leftchild!=NULL) return LAMBDA;
  i->leftchild->label=l;
  i->leftchild->leftchild=i->leftchild->rightchild=NULL;
  return i->leftchild;
}

node BiInsertRightChild(labeltype l, node i, BinaryTree *Tp){
  if(i==NULL) exit(8);  // nije definirana
  if(i->rightchild!=NULL) return LAMBDA;
  i->rightchild->label=l;
  i->rightchild->leftchild=i->rightchild->rightchild=NULL;
  return i->rightchild;
}

void BiDelete(node i, BinaryTree *Tp){
  if(i==NULL) exit(1);
  if(i->leftchild!=NULL || i->rightchild!=NULL) exit(1);
  i=NULL;
}

node BiRoot(BinaryTree T){
  if(T==NULL)
    return LAMBDA;
  return T;
}

node BiLeftChild(node i, BinaryTree T){
  if(i->leftchild==NULL)
    return LAMBDA;
  return i->leftchild;
}

node BiRightChild(node i, BinaryTree T){
  if(i->rightchild==NULL)
    return LAMBDA;
  return i->rightchild;
}

void roditelj(node *otac, node i, node kor, BinaryTree T) {  //pomocna funkcija
  if (BiLeftChild(i, T)== i || BiRightChild(i, T)== i)
    *otac = kor;
  if (*otac)
    return;
  if (BiLeftChild(i, T))
    roditelj(otac, i, BiLeftChild(i, T),T);
  if (BiRightChild(i, T))
    roditelj(otac, i, BiRightChild(i, T),T);
}

node BiParent(node i, BinaryTree T){
  if(i==NULL) exit(8);  //nije definirana
  if(i==T) return LAMBDA;
  node otac=BiCreate();
  roditelj(&otac, i, T, T);
  return otac;
}

labeltype BiLabel(node i, BinaryTree T){
  if(i==NULL) exit(8); //nije definirana
  return i->label;
}

void BiChangeLabel(labeltype l, node i, BinaryTree *Tp){
  if(i==NULL) exit(8); //nije definirana
  i->label=l;
}


int search(char arr[], int strt, int end, char value);

struct node* newNode(char data);

struct node* buildTree(char in[], char pre[], int inStrt, int inEnd){
  static int preIndex =(sizeof(pre)/sizeof(pre[0]))-1; //zadnji u postorderu je korjen

  if(inStrt > inEnd){
    return NULL;
  }
  struct node *tNode = newNode(pre[preIndex--]);   //krecem se od iza zbog defiicje postordera

  if(inStrt == inEnd)       //tu nam je bazicni slucaj
    return tNode;

  int inIndex = search(in, inStrt, inEnd, tNode->data);
  tNode->right = buildTree(in, pre, inIndex+1, inEnd);
  tNode->left= buildTree(in, pre, inStrt, inIndex-1);
  return tNode;
}

int search(char arr[], int strt, int end, char value){ //pomocna funkcija za trazenje znaka
  int i;
  for(i = strt; i <= end; i++){
    if(arr[i] == value)
      return i;
  }
}


struct node* newNode(char znak){  //stvaram novi cvor
  struct node* node = (struct node*)malloc(sizeof(struct node));
  BiLabel(newNode, T)=znak;
  BiLeftChild(newNode, T)=LAMDA;
  BiRightChild(newNode, T)=LAMDA;
  return(node);
}


void print_tree(struct node* node, int l, BinaryTree T){
  int i;
  if(!node) return;
  printf ("%c", Bilabel(node, T));
  if (BiLeftChild(node, T)!=NULL) printf(" %c", Bilabel((BiLeftChild(node, T)), T));
  else printf ("  NULL");
  if (BiRightChild(node, T)!=NULL) printf(" %c", Bilabel((BiRightChild(node, T)), T));
  else printf ("  NULL");
  printf ("\n");
  printf("---------------\n");
  print_tree(BiLeftChild(node, T), l+1, T);
  print_tree(BiRightChild(node,T) l+1, T);
}


int main(){
  BinaryTree T;
  BiMakeNull(&T);
  char in[] = {'D', 'G', 'B', 'F', 'C', 'E', 'A'};
  char pre[] = {'G', 'D', 'F', 'E', 'C', 'A', 'B'};
  int len = sizeof(in)/sizeof(in[0]);
  struct node *root = buildTree(in, pre, 0, len - 1);
  print_tree(root, len, T);
  return 0;
}