#include<stdio.h>
 #include "stabla.h"
 
 Cvor* pretrazi_stablo(Cvor* koren, int broj)
{
	if(koren == NULL)
		return NULL;
	
	if(koren->vrednost == broj)
		return koren;
	else if(broj < koren->vrednost)
		return pretrazi_stablo(koren->levo, broj);
	else
		return pretrazi_stablo(koren->desno, broj);
}

Cvor* pronadji_najmanji(Cvor* koren)
{
	if(koren == NULL)
		return NULL;
	if(koren->levo == NULL)
		return koren;
	return pronadji_najmanji(koren->levo);
}

Cvor* pronadji_najveci(Cvor* koren)
{
	if(koren == NULL)
		return NULL;
	if(koren->desno == NULL)
		return koren;
	return pronadji_najveci(koren->desno);
}

void obrisi_element(Cvor** koren, int broj)
{
	/* Ako je stablo prazno, nema potrebe za brisanjem  */
	if(*koren == NULL)
		return;
	
	/* Ako je broj koji treba obrisati manji od vrednosti u
     korenu stabla, broj se eventualno nalazi u levom podstablu, te
     je potrebno rekurzivno primeniti postupak na levo podstablo. Koren
     ovako modifikovanog stabla je nepromenjen. */
	
	if(broj < (*koren)->vrednost)
	{
		obrisi_element(&(*koren)->levo, broj);
		return;
	}  
	/* Slicna situacija kretanja nadesno - ako je broj veci od vrednosti u korenu stabla */
	else if(broj > (*koren)->vrednost)
	{
		obrisi_element(&(*koren)->desno, broj);
		return;
	}
	else{
		/* Slede podslucajevi vezani za slucaj kada je vrednost u korenu
     jednaka broju koji se brise tj. slucaj kada treba obrisati
     koren */
		
		/* 1. slucaj: ako koren nema sinova, tada se on prosto brise, i rezultat
          je prazno stablo (vraca se NULL) */
		if((*koren)->levo == NULL && (*koren)->desno == NULL)
		{
			free(*koren);
			*koren = NULL;
		} 
		/* 2. slucaj: ako koren ima samo desnog sina, tada se brisanje vrsi tako
         sto se brise koren, a novi koren postaje desni sin */
		else if((*koren)->levo == NULL) 
		{
			Cvor* tmp = *koren;
			*koren = (*koren)->desno;
			free(tmp);
		}
		/* 3. slucaj: Ako koren ima samo levog sina, tada se brisanje vrsi tako
           sto se brise koren, a novi koren postaje levi sin */
		else if((*koren)->desno == NULL) 
		{
			Cvor* tmp = *koren;
			*koren = (*koren)->levo;
			free(tmp);
		}else{ 
		     /* 4.slucaj: Ako koren ima oba sina, najpre se potrazi sledbenik korena
     (u smislu poretka) u stablu. To je upravo po vrednosti
     najmanji cvor u desnom podstablu koji se moze pronaci npr.
     funkcijom pronadji_najmanji(). Potom se u koren smesti
     vrednost pronadjenog cvora, a u taj cvor se smesti vrednost
     korena (tj. broj koji se brise). Zatim se rekurzivno pozove
     funkcija za brisanje nad desnim podstablom. S obzirom da u
     njemu treba obrisati najmanji element, a on zasigurno ima
     najvise jednog potomka, jasno je da ce njegovo brisanje biti
     obavljeno na jedan od jednostavnijih nacina koji su gore
     opisani. */
		
			Cvor* sl = pronadji_najmanji((*koren)->desno);
			
			//zamenimo im vrednosti
			(*koren)->vrednost = sl->vrednost;
			sl->vrednost = broj;
			
			//pozovemo brisanje elementa u desnom podstablu
			obrisi_element(&(*koren)->desno, broj);
		}
	}
}

 
 int main()
 {
        //Obavezna inicijalizacija stabla
	Cvor* s = NULL;
	
	ucitaj_stablo(&s, stdin);
	Cvor * min = pronadji_najmanji(s);
	
	ispisi_stablo(s, stdout);
	printf("\n");
	
	if(min != NULL)
		printf("Najmanji clan: %d\n", min->vrednost);
	
	obrisi_element(&s, 5);
	ispisi_stablo(s, stdout);
	printf("\n");
	
	oslobodi_stablo(s);
 return 0;
 }