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

//vrijeme izvrsavanja konstantno

typedef char* labeltype; //oznaka cvora(jer su nam ulazni podaci stringovi)

typedef struct cell_tag{ //svaki cvor prikazujemo jednom celijom
 labeltype label; //oznaka cvora
 struct cell_tag *leftchild;  //pointer na lijevo dijete
 struct cell_tag *rightchild; //pointer na desno dijete
}celltype;

typedef celltype *node;  //cvor je odreden pointerom na tu celiju
typedef celltype *BinaryTree;  //binarno stablo poistovjecujemo s pointerom na korjen

void BiMakeNull(BinaryTree *Tp){ //stavljamo pointer na stablo na null pointer
  *Tp=NULL;
}

int BiEmpty(BinaryTree T){ //provjera je li nase stablo prazno
  if(T==NULL)return 1;
  return 0;
}

void BiCreate(labeltype l, BinaryTree TL, BinaryTree TR, BinaryTree *Tp){ //kreiramo novo
 (*Tp)=(celltype*)malloc(sizeof(celltype)); //alociramo memoriju
 (*Tp)->label=l;   //oznaka
 (*Tp)->leftchild=TL; //lijevo dijete
 (*Tp)->rightchild=TR; //desno dijete
}

void BiLeftSubtree(BinaryTree T, BinaryTree *TLp){
  (*TLp)=T->leftchild; //vracamo lijevo podstablo
}

void BiRightSubtree (BinaryTree T, BinaryTree *TRp){         //vraca deno podstablo
    (*TRp)=T->rightchild; //vracamo desno podstablo
}
node BiInsertLeftChild(labeltype l, node i, BinaryTree *Tp){    //umetanje lijevog djeteta
    if (!i){
    printf("Takav cvor ne postoji.");
    exit(2);                                                             //exit(2)->ne postoji cvor kome bi umetnuli lijevo dijete
    }
    if (i->leftchild != NULL){
    printf("Takav cvor vec ima lijevo dijete.");                         //exit(4)-> cvor vec ima lijevo dijete
    exit(4);
   }
    if (!(i->leftchild = (celltype*)malloc(sizeof(celltype)))){           //provjera ima li memorije za cvor
    printf("Mem out.");
    exit(8);                                                              //exit(8)->Nemam memorije za novi cvor
   }

    i->leftchild->label = l;                                              //oznaka cvora je l
    i->leftchild->leftchild = i->leftchild->rightchild = NULL;            //pointeri na lijevo i desno dijete novog cvora su NULL

    return i->leftchild;                                                  //funkcija vraca pointer na novi cvor
    }

node BiInsertRightChild(labeltype l, node i, BinaryTree *Tp){   //umetanje desnog djeteta
    if (!i){
    printf("Takav cvor ne postoji.");
    exit(2);                                                               //exit(2)->ne postoji cvor kome bi umetnuli desno dijete
    }

    if (i->rightchild != NULL){
    printf("Takav cvor vec ima desno dijete.");
    exit(4);                                                                //exit(4)-> cvor vec ima desno dijete
    }

    if (!(i->rightchild = (celltype*)malloc(sizeof(celltype)))){
    printf("Mem out.");
    exit(8);                                                                 //exit(8)->Nemam memorije za novi cvor
    }

    i->rightchild->label = l;                                                 //oznaka cvora je l
    i->rightchild->leftchild = i->rightchild->rightchild = NULL;              //pointeri na lijevo i desno dijete novog cvora su NULL

    return i->rightchild;                                                     //funkcija vraca pointer na novi cvor
    }

node BiRoot(BinaryTree T){       //vraca korijen binarnog stabla
    return T;
}

node BiLeftChild( node i, BinaryTree T){   //vraca lijevo dijete cvora
  if (!i)
    return LAMBDA;
  if (i->leftchild == NULL)
    return LAMBDA;

return i->leftchild;
}

node BiRightChild(node i, BinaryTree T){    //vraca desno dijete cvora
  if (i==NULL)
    return LAMBDA;
  if (i->rightchild == NULL)
   return LAMBDA;

return i->rightchild;
}

void ParentSearch(node *parent, node i, node root){     //pomocna funkcija, trazi roditelja od cvora
  if ((root->leftchild == i) || (root->rightchild == i))
        *parent = root;
  if (*parent) return;
  if (root->leftchild)
    ParentSearch(parent, i, root->leftchild);
  if (root->rightchild)
  ParentSearch(parent, i, root->rightchild);
}

node BiParent(node i, BinaryTree T){      // vraca roditelja od cvora
  if (!i){
    printf("Taj cvor ne postoji.");
    exit(1);
    }
  if(i == T)  //korjen nema cvora
    return NULL;
  node roditelj = NULL;
  ParentSearch(&roditelj, i, T);
    return roditelj;
}

labeltype BiLabel(node i, BinaryTree T){  //vraca oznaku cvora
  if (i==NULL){
     printf ("Takav cvor ne postoji");
     exit(2);
    }
  return i->label;
}

void BiChangeLabel(labeltype l,node i, BinaryTree *Tp){  // mijenja oznaku cvora
  if (i==NULL){
    printf("Takav cvor ne postoji");
    exit(2);
  }
  i->label = l;
}

void BiDelete(node i, BinaryTree *Tp){ //izbacujemo list i iz stabla
  if (!i){
    printf("Takav cvor ne postoji.");
    exit(2);
    }
  if (i->rightchild || i->leftchild){ //nije list
    printf("Taj cvor ima dijete pa se ne moze izbrisati!");
    exit(16);
    }
  node r=BiParent(i, *Tp);
  if (r==LAMBDA){ //taj list je ujutro i korjen
      free (Tp);
      return;
    }
  if ( BiLeftChild(r,*Tp)==i)
    r->leftchild=NULL;
  else
  r->rightchild==NULL; //roditelja ostavljamo bez djeteta
    free(i);  //oslobadamo memoriju
}

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->left= buildTree(in, pre, inStrt, inIndex-1);
  tNode->right = buildTree(in, pre, inIndex+1, inEnd);
  return tNode;
}

int search(char arr[], int strt, int end, char value){
 int i;
 for(i = strt; i <= end; i++){
   if(arr[i] == value)
    return i;
    }
}


struct node* newNode(char data){
  struct node* node = (struct node*)malloc(sizeof(struct node));
  node->data = data;
  node->left = NULL;
  node->right = NULL;
  return(node);
}
void print_tree(struct node* node, int l){
  int i;
  if(!node) return;
  printf ("%c", node->data);
  if (node->left!=NULL) printf(" %c", node->left->data);
   else printf ("  NULL");
  if (node->right!=NULL) printf(" %c", node->right->data);
   else printf ("  NULL");
  printf ("\n");
  print_tree(node->left, l+1);
  print_tree(node->right, l+1);
}

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);
 return 0;
}