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

typedef struct cvor_stabla {
  int podatak;
  struct cvor_stabla *levi, *desni;
} cvor;

cvor* napravi_cvor(int podatak) {
  cvor* novi=malloc(sizeof(cvor));
  if(novi==NULL)
    return NULL;
  novi->podatak=podatak;
  novi->levi=NULL;
  novi->desni=NULL;
  return novi;
}

int dodaj_u_stablo_iterativno(cvor** k, int podatak) {  
  while(*k!=NULL) {
    if(podatak < (*k)->podatak)
      k=&((*k)->levi);
    else
      k=&((*k)->desni);
  }
  *k=napravi_cvor(podatak);
  if(*k==NULL)
    return 0;
  return 1;
}

int dodaj_u_stablo_rekurzivno(cvor** k, int podatak) {
  if(*k == NULL) {
    *k=napravi_cvor(podatak);
    if(*k==NULL)
      return 0;
    return 1;
  }
  else if(podatak<(*k)->podatak)
    return dodaj_u_stablo_rekurzivno(&((*k)->levi), podatak);
  else
    return dodaj_u_stablo_rekurzivno(&((*k)->desni), podatak);
}

void obrisi_stablo1(cvor* k) {
  if(k!=NULL) {
    obrisi_stablo(k->levi);
    obrisi_stablo(k->desni);
    free(k);    
  }
}

void obrisi_stablo2(cvor** k) {
  if(*k!=NULL) {
    obrisi_stablo(&((*k)->levi));
    obrisi_stablo(&((*k)->desni));
    free(*k);    
    *k=NULL;
  }
}



cvor* pronadji_cvor(cvor* koren, int podatak) {
  if(koren==NULL)
    return NULL;
  if(podatak == koren->podatak)
    return koren;
  if(podatak < koren->podatak)
    return pronadji_cvor(koren->levi, podatak);
  return pronadji_cvor(koren->desni, podatak);
}

void ispisi_stablo_infix(cvor* koren) {
  if(koren!=NULL) {
    ispisi_stablo_infix(koren->levi);
    printf("%d\n",koren->podatak);
    ispisi_stablo_infix(koren->desni);
  }
}

void ispisi_stablo_prefix(cvor* koren) {
  if(koren!=NULL) {
    printf("%d\n",koren->podatak);
    ispisi_stablo_prefix(koren->levi);
    ispisi_stablo_prefix(koren->desni);
  }
}

void ispisi_stablo_postfix(cvor* koren) {
  if(koren!=NULL) {
    ispisi_stablo_postfix(koren->levi);
    ispisi_stablo_postfix(koren->desni);
    printf("%d\n",koren->podatak);
  }
}

cvor* pronadji_minimum(cvor* koren) {
  if(koren==NULL)
    return NULL;
  if(koren->levi==NULL)
    return koren;
  return pronadji_minimum(koren->levi);
}

void obrisi_cvor(cvor** k, int podatak) {
  cvor* pomocni;
  cvor* koren=*k;
  if(koren==NULL)
    return;
  if(podatak < koren->podatak) {
    obrisi_cvor(&(koren->levi), podatak);
    return;
  }
  else if(podatak > koren->podatak) {
    obrisi_cvor(&(koren->desni), podatak);
    return;
  }
  
  obrisi_cvor(&(koren->desni), podatak);
  
  if(koren->levi == NULL && koren->desni == NULL) {
    *k=NULL;
    free(koren);
    return;
  }

  if(koren->levi != NULL && koren->desni == NULL) {
    (*k)=koren->levi;
    free(koren);
    return;
  }

  if(koren->levi == NULL && koren->desni != NULL) {
    (*k)=koren->desni;
    free(koren);
    return;
  }
  
  pomocni=pronadji_minimum(koren->desni);
  koren->podatak=pomocni->podatak;
  pomocni->podatak=podatak;
  obrisi_cvor(&(koren->desni), podatak);
}

int main(int argc, char** argv) {
  cvor* koren=NULL;
  cvor* t;
  int n;

  printf("Unesite podatke:\n");
  while(scanf("%d",&n)!=EOF) 
    dodaj_u_stablo_iterativno(&koren,n);
  printf("Stablo je napravljeno.\n");
  printf("Infiksno:\n");
  ispisi_stablo_infix(koren);
  printf("Prefiksno:\n");
  ispisi_stablo_prefix(koren);
  printf("Postfiksno:\n");
  ispisi_stablo_postfix(koren);

  printf("Unesite podatak koji se razi:\n");  
  scanf("%d",&n);
  
  t=pronadji_cvor(koren, n);
  if(t!=NULL)
    printf("Cvor je nadjen!\n");
  else
    printf("Cvor nije nadjen!\n");

  scanf("%d",&n);
  obrisi_cvor(&koren, n);
  ispisi_stablo_infix(koren);
  obrisi_stablo2(&koren);
  return 0;
}