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

typedef char labeltype;

typedef struct celltype{
  labeltype label;
  struct celltype *leftchild;
  struct celltype *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;
  BiCreate(l, NULL, NULL, i->leftchild);
  return i->leftchild;
}

node BiInsertRightChild(labeltype l, node i, BinaryTree *Tp){
  if(i==NULL) exit(8);  // nije definirana
  if(i->rightchild!=NULL) return LAMBDA;
  BiCreate(l, NULL, NULL, i->rightchild);
  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=NULL;
  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);

node* newNode(char label);

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 LAMBDA;
  }
  node *tNode;   //krecem se od iza zbog defiicje postordera
  BiCreate(pre[preIndex--], NULL, NULL, *tNode);

  if(inStrt == inEnd)       //tu nam je bazicni slucaj
    return (*tNode);
  int inIndex = search(in, inStrt, inEnd, pre[preIndex--]);
  (*tNode)->rightchild = buildTree(in, pre, inIndex+1, inEnd);
  (*tNode)->leftchild= 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;
  }
}


void print_tree(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]);
  node *root = buildTree(in, pre, 0, len - 1);
  print_tree(root, len, T);
  return 0;
}