#include <stdio.h>
#include <conio.h>
#include <malloc.h>


struct arbore {
                int k;
                struct arbore *ss,*sd;
              };


struct arbore *init_arbore_binar()
{
    struct arbore *aux;
    char nn,c1;
    int k;

    printf(" e nod NULL ? ");
    scanf("%c",&nn);
    c1=getchar();
    if ((nn== 'n')||(nn== 'N'))
		{
		    printf(" cheie : ");
            scanf("%d",&k);
            c1=getchar();
            aux=(struct arbore *) malloc(sizeof(struct arbore));
            aux->k=k;
            printf("Fiul stang al lui %d",k);
            aux->ss=init_arbore_binar();
            printf("Fiul drept al lui %d",k);
            aux->sd=init_arbore_binar();
            return aux;
		}
  else
    return NULL;
}

void RSD( struct arbore *a)
{
    if(a)
	{
	    printf("%d ",a->k);
        RSD(a->ss);
        RSD(a->sd);
	}
}

void SRD( struct arbore *a)
{
    if(a)
	{
        SRD(a->ss);
        printf("%d ",a->k);
        SRD(a->sd);
	}
}

// 10. Sa se caute o cheie in arborele binar;
int cautare_cheie_in_arborele_binar(struct arbore *a, int key){
     static int valid_boolean = 0;
    if(a){
        if(a->k == key){
            valid_boolean = 1;
        }
    cautare_cheie_in_arborele_binar(a->ss, key);
    cautare_cheie_in_arborele_binar(a->sd, key);
    return valid_boolean;
    }
}

//11. Sa se afiseze elementele aflate in intervalul [a,b];

void afisare_elemente_interval(struct arbore *a, int cap, int coada){
    if(a){
        if(a->k >= cap && a->k <=coada){
            printf("%d ", a->k);
        }
    afisare_elemente_interval(a->ss, cap, coada);
    afisare_elemente_interval(a->sd, cap, coada);
    }
}

//18. Sa se determine numarul de noduri 0, 1, respectiv 2 fii dintr-un arbore binar;

int noduri_cu_0_fii(struct arbore *a){
    int static noduri_cu_0_fii_var  = 0;
    if(a){
        if(!a->ss && !a->sd){
            noduri_cu_0_fii_var++;
        }
        noduri_cu_0_fii(a->ss);
        noduri_cu_0_fii(a->sd);
        return noduri_cu_0_fii_var;
    }
}

int noduri_cu_1_fii(struct arbore *a){
    int static noduri_cu_1_fiu_var = 0;
    if(a){
        if((!a->ss && a->sd) || (a->ss && !a->sd)){
            noduri_cu_1_fiu_var++;
        }
        noduri_cu_1_fii(a->ss);
        noduri_cu_1_fii(a->sd);
        return noduri_cu_1_fiu_var;
    }
}

int noduri_cu_2_fii(struct arbore *a){
    int static noduri_cu_2_fii_var = 0;
    if(a){
        if(a->ss && a->sd){
            noduri_cu_2_fii_var++;
        }
        noduri_cu_2_fii(a->ss);
        noduri_cu_2_fii(a->sd);
        return noduri_cu_2_fii_var;
    }
}

int max(int a, int b){
    return a>b?a:b;
}

int afisare_nivel_arbore(struct arbore *a){
    int static inaltime = 0;
    if(a){
        return 1+max(afisare_nivel_arbore(a->ss), afisare_nivel_arbore(a->sd));
    }else{
        return 0;
    }
}

//Aflare arbore echilibrat
 int arbore_echilibrat(struct arbore *a){
     int static arbore_echilibrat_var = 0;
    if(a){
        if(afisare_nivel_arbore(a->ss) == afisare_nivel_arbore(a->sd)){
            arbore_echilibrat(a->ss);
            arbore_echilibrat(a->sd);
            arbore_echilibrat_var = 1;
            arbore_echilibrat_var;
        }else{
        arbore_echilibrat_var = 0;
        return arbore_echilibrat_var;
        }
    }
 }


int main()
{
    struct arbore *a;

    printf("Radacina");
	a=init_arbore_binar();
	printf("Parcurgerea RSD : ");
	RSD(a);
	// printf("\n\n\n\n\n   %d", cautare_cheie_in_arborele_binar(a, 2));
	printf("\n\n\n\n\n");
	//afisare_elemente_interval(a, 6, 8);


    //Afisare fii arborelui
	//printf("Noduri cu 0 fii:  %d\n", noduri_cu_0_fii(a));
    //printf("Noduri cu 1 fiu:  %d\n", noduri_cu_1_fii(a));
    //printf("Noduri cu 2 fii:  %d\n", noduri_cu_2_fii(a));
   // printf("%d", afisare_nivel_arbore(a));
     printf("%d", arbore_echilibrat(a));
	return 0;
}


// n 3 n 4 d d n 7 n 5 d d n 2 n 1 d n 8 d d d