#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define LAMBDA NULL

typedef char *labeltype;

typedef struct celltag {
labeltype label;             //oznaka cvora
struct celltag *leftchild;   // pointer na lijevo dijete
struct celltag *rightchild;  // pointer na desno dijete
} celltype;

typedef struct node{
  char data;
  struct node* left;
  struct node* right;
};

typedef celltype *node;

typedef celltype *BinaryTree;

void BiMakeNull(BinaryTree *T){ //radi prazno stablo, stavlja pointer na stablo na NULL
    *T=NULL;
}

int BiEmpty (BinaryTree T){   //provjerava je li stablo prazno
    if (T) return 0;
    else return 1;
}

void BiCreate (labeltype l, BinaryTree TL, BinaryTree TR, BinaryTree *T) {  //kreira novo stablo
    *T = (celltype*)malloc(sizeof(celltype));                               //alokacija memorije za korijen
    (*T)->label = l;                                                        //oznaka korijena
    (*T)->leftchild = TL;                                                   //stvaranje lijevog podstabla
    (*T)->rightchild = TR;                                                  //stvaranje desnog podstabla
    }

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

 void BiRightSubtree (BinaryTree T, BinaryTree *TR){                      //vraca deno podstablo
    *TR=T->rightchild;
    }

node BiInsertLeftChild(labeltype l, node i, BinaryTree *T){              //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 *T){               //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) return NULL;
    node roditelj = NULL;
    ParentSearch(&roditelj, i, T);
    return roditelj;
    }

void BiDelete(node i, BinaryTree *T){                                          // brise cvor
    if (!i){
    printf("Takav cvor ne postoji.");
    exit(2);
    }

    if (i->rightchild || i->leftchild){
    printf("Taj cvor ima dijete pa se ne moze izbrisati!");
    exit(16);
    }
    node r=BiParent(i, *T);
    if (r==LAMBDA){
        free (T);
        return;
    }
    if ( BiLeftChild(r,*T)==i ) r->leftchild=NULL;
    else r->rightchild==NULL;
    free(i);
    }


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 *T){                  // mijenja oznaku cvora
    if (i==NULL){
    printf("Takav cvor ne postoji");
    exit(2);
    }
    i->label = l;
}
/*gotova implementacija binarnog stabla*/




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;
    }