#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAXLENGTH 1023
#define LAMBDA -1
#define PRAZNO -1

typedef char labeltype;
typedef int node;

//implementacija

typedef struct {
    node last;
    labeltype labels[MAXLENGTH];
} BTREE;

void MAKE_NULL(BTREE *);
int EMPTY(BTREE);
//void kopiraj_stablo(BTREE, BTREE *, node, node);
node CREATE(labeltype, BTREE, BTREE, BTREE *);
void LEFT_SUBTREE(BTREE, BTREE *);
void RIGHT_SUBTREE(BTREE, BTREE *);
node INSERT_LEFT_CHILD(labeltype, node, BTREE *);
node INSERT_RIGHT_CHILD(labeltype, node, BTREE *);
void DELETE(node, BTREE *);
node ROOT(BTREE);
node LEFT_CHILD(node, BTREE);
node RIGHT_CHILD(node, BTREE);
node PARENT(node, BTREE);
labeltype LABEL(node, BTREE);
void CHANGE_LABEL(labeltype, node, BTREE *);

void MAKE_NULL(BTREE *T) {
  int i;
  for (i = 0; i < MAXLENGTH; ++i)
    T->labels[i] = PRAZNO;
}

int EMPTY(BTREE T) {
  return T.labels[0] == PRAZNO;
}

/*void kopiraj_stablo(BTREE T1, BTREE *T2, node i, node j) {
  MAKE_NULL(T2);
  if (i < 0 || i >= MAXLENGTH || T1.labels[i] == PRAZNO)
    return;
  if (j < 0 || j >= MAXLENGTH)
    return;
  T2->labels[j] = T1.labels[i];
  kopiraj_stablo(T1, T2, 2 * i + 1, 2 * j + 1);
  kopiraj_stablo(T1, T2, 2 * i + 2, 2 * j + 2);
}

node CREATE(labeltype l, BTREE TL, BTREE TR, BTREE *T) {
  T->labels[0] = l;
  kopiraj_stablo(TL, T, 0, 1);
  kopiraj_stablo(TR, T, 0, 2);
  return 0;
}*/

//

void fun(node i, BTREE *T, node j, BTREE *T1) {
    if (j >= MAXLENGTH || i >= MAXLENGTH || 2*i>=MAXLENGTH || 2*j>=MAXLENGTH) return;
    T->labels[i] = T1->labels[j];
    fun(2*i + 1, T, 2*j + 1, T1);
    fun(2*i + 2, T, 2*j + 2, T1);
}

node CREATE(labeltype l, BTREE TL, BTREE TR, BTREE *T) {
    T->labels[0]=l;
    fun(1, T, 0, &TL);
    fun(2, T, 0, &TR);
    return 0;
}

//

void LEFT_SUBTREE(BTREE T, BTREE *TL) {
  //kopiraj_stablo(T, TL, 1, 0);
    fun(0, TL, 1, &T);
}

void RIGHT_SUBTREE(BTREE T, BTREE *TR) {
  //kopiraj_stablo(T, TR, 2, 0);
    fun(0, TR, 2, &T);
}

node INSERT_LEFT_CHILD(labeltype l, node i, BTREE *T) {
  if (i < 0 || i >= MAXLENGTH || T->labels[i] == PRAZNO) {
    printf("INSERT_LEFT_CHILD: Ne postoji taj cvor.");
    exit(1);
  }
  if (2 * i + 1 >= MAXLENGTH) {
    printf("INSERT_LEFT_CHILD: Ne mogu dodati lijevo dijete.");
    exit(1);
  }
  T->labels[2 * i + 1] = l;
  return 2 * i + 1;
}

node INSERT_RIGHT_CHILD(labeltype l, node i, BTREE *T) {
  if (i < 0 || i >= MAXLENGTH || T->labels[i] == PRAZNO) {
    printf("INSERT_RIGHT_CHILD: Ne postoji taj cvor.");
    exit(1);
  }
  if (2 * i + 2 >= MAXLENGTH) {
    printf("INSERT_RIGHT_CHILD: Ne mogu dodati desno dijete.");
    exit(1);
  }
  T->labels[2 * i + 2] = l;
  return 2 * i + 2;
}

void DELETE(node i, BTREE *T) {
  if (i < 0 || i >= MAXLENGTH || T->labels[i] == PRAZNO) {
    printf("DELETE: Ne postoji taj cvor.");
    exit(1);
  }
  if (2 * i + 1 < MAXLENGTH && T->labels[2 * i + 1] != PRAZNO) {
    printf("DELETE: Cvor ima dijete.");
    exit(1);
  }
  if (2 * i + 2 < MAXLENGTH && T->labels[2 * i + 2] != PRAZNO) {
    printf("DELETE: Cvor ima dijete.");
    exit(1);
  }
  T->labels[i] = PRAZNO;
}

node ROOT(BTREE T) {
  if (T.labels[0] == PRAZNO)
    return LAMBDA;
  return 0;
}

node LEFT_CHILD(node i, BTREE T) {
  if (i < 0 || i >= MAXLENGTH || T.labels[i] == PRAZNO) {
    printf("LEFT_CHILD: Ne postoji taj cvor.");
    exit(1);
  }
  if (2 * i + 1 >= MAXLENGTH || T.labels[2 * i + 1] == PRAZNO)
    return LAMBDA;
  return 2 * i + 1;
}

node RIGHT_CHILD(node i, BTREE T) {
  if (i < 0 || i >= MAXLENGTH || T.labels[i] == PRAZNO) {
    printf("RIGHT_CHILD: Ne postoji taj cvor.");
    exit(1);
  }
  if (2 * i + 2 >= MAXLENGTH || T.labels[2 * i + 2] == PRAZNO)
    return LAMBDA;
  return 2 * i + 2;
}

node PARENT(node i, BTREE T) {
  if (i < 0 || i >= MAXLENGTH || T.labels[i] == PRAZNO) {
    printf("PARENT: Ne postoji taj cvor.");
    exit(1);
  }
  if (i == 0)
    return LAMBDA;
  return (i - 1) / 2;
}

labeltype LABEL(node i, BTREE T) {
  if (i < 0 || i >= MAXLENGTH || T.labels[i] == PRAZNO) {
    printf("LABEL: Ne postoji taj cvor.");
    exit(1);
  }
  return T.labels[i];
}

void CHANGE_LABEL(labeltype l, node i, BTREE *T) {
  if (i < 0 || i >= MAXLENGTH || T->labels[i] == PRAZNO) {
    printf("CHANGE_LABEL: Ne postoji taj cvor.");
    exit(1);
  }
  T->labels[i] = l;
}


//kraj implementacije

char upis[100];
int j=0,tst=0;

void kreiraj (BTREE *B, int n) {
    printf("\n u funkciji %d. put\n", tst);
    tst++;
    BTREE TL, TR;
    MAKE_NULL(&TL);
    MAKE_NULL(&TR);
    labeltype k;
    if(j>=n)
        return;
    k=upis[j];
    if(k=='N')
    {
        j=j+4;
        return;
    }
    else
        j++;
    kreiraj(&TL, n);
    kreiraj(&TR, n);
    CREATE(k, TL, TR, B);
}

int broj_listova (node n, BTREE B) {
    int l=0;
    if(n==NULL) return 0;
    if(LEFT_CHILD(n, B)==LAMBDA && RIGHT_CHILD(n, B)==LAMBDA)
        l=1;
    return (l + broj_listova(LEFT_CHILD(n, B), B) + broj_listova(RIGHT_CHILD(n, B), B));
}

void ispis_listova (node n, BTREE B) {
    if(n==NULL) return;
    if(LEFT_CHILD(n, B)==LAMBDA && RIGHT_CHILD(n, B)==LAMBDA)
        printf("%s ", LABEL(n, B));
    ispis_listova(LEFT_CHILD(n, B), B);
    ispis_listova(RIGHT_CHILD(n, B), B);
}

int main(void) {
    BTREE B;
    int i=0,br=0;
    MAKE_NULL(&B);
    gets(upis);
    while(upis[i]!='\0')
{
    if(upis[i]=='N')
    {
        br++;
        i=i+4;
    }
    else
    {
    i++;
    br++;
    }
}
    printf("\n i:%d br: %d upis od 2:%c", i,br, upis[2]);
    kreiraj(&B,br);
    printf("\n funkcija kreiraj gotova");
    printf("\n oznaka drugog čvora %c", LABEL(2,B));
    printf("\n %d: ", broj_listova(ROOT(B),B));
    ispis_listova(ROOT(B),B);
    return 0;
}