#include <iostream>
using namespace std;

//I
// (a) va descurcați sa faceți desenu

// (b)

struct Nod {
    int info;
    int nrFii;
    Nod** adrFii;
};
Nod* creareArbore(int* parinte, int nr) {
    Nod** noduri = new Nod*[nr];
    Nod* radacina = nullptr;
    for (int i = 0; i < nr; ++i) {
        noduri[i] = new Nod;
        noduri[i]->info = i;
    }
    for (int i = 0; i < nr; ++i) {
        Nod* n = noduri[i];
        if (parinte[i] == -1) radacina = n;
        //am putea sa numaram cati fii are, da e mai simplu asa
        // (putem avea maxim nr-1 fii)
        n->adrFii = new Nod*[nr - 1];
        for (int j = 0; j < nr; ++j) {
            if (parinte[j] == i) {
                n->adrFii[n->nrFii] = noduri[j];
                n->nrFii++;
            }
        }
    }
    delete[] noduri;
    return radacina;
}
//se poate si folosind liste inlantuite, dar e mai scurt asa
Nod** coada;
int vfCoada = 0;
int sfCoada = 0;
void adaugareCoada(Nod* n) {
    coada[sfCoada] = n;
    sfCoada++;
}

Nod* stergereCoada() {//suna dubios
    Nod* n = coada[vfCoada];
    ++vfCoada;
    return n;
}
bool coadaAreElemente() {
    return vfCoada != sfCoada;
}

void afisareNivele(Nod* rad) {
    vfCoada = 0;
    sfCoada = 0;
    adaugareCoada(rad);
    while (coadaAreElemente()) {
        Nod* n = stergereCoada();
        cout << n->info << " ";
        for (int i = 0; i < n->nrFii; ++i)
            adaugareCoada(n->adrFii[i]);
    }
    cout << endl;
}
// (c)
void afisareNoduriTerminale(Nod* n) {
    if (n->nrFii == 0) {
        cout << n->info << " ";
    } else {
        for (int i = 0; i < n->nrFii; ++i)
            afisareNoduriTerminale(n->adrFii[i]);
    }
}
//(d)
Nod* stanga(Nod *n) {
    if (n->nrFii == 0) return nullptr;
    return n->adrFii[0];
}

Nod* dreapta(Nod *n) {
    if (n->nrFii <= 1) return nullptr;
    return n->adrFii[1];
}
bool esteBinar(Nod* n) {
    if (n->nrFii > 2) return false;
    for (int i = 0; i < n->nrFii; i++) {
        if (!esteBinar(n->adrFii[i])) return false;
    }
    return true;
}
int max(int a, int b){
    return a>b ? a:b;}
int inaltime(Nod* p) {
    if(p==0) return -1;
    int hs=inaltime(stanga(p));
    int hd=inaltime(dreapta(p));
    return max(hs,hd)+1;
}

bool esteEchilibrat(Nod* n) {
    if (n == nullptr) return true;
    if (!esteEchilibrat(stanga(n))) return false;
    if (!esteEchilibrat(dreapta(n))) return false;
    int factor = inaltime(dreapta(n)) - inaltime(stanga(n));
    return factor >= -1 && factor <= 1;
}
bool esteAVL(Nod* n) {
    if (!esteBinar(n)) return false;
    return esteEchilibrat(n);
}
int main() {
    // (b)
    //presupunand ca indexarea incepe de la 0 (cum ar trebui)
    //               0, 1, 2, 3, 4, 5, 6, 7, 8
    int parinte[] = {1, 3, 1,-1, 5, 3, 7, 5, 7};
    int nr = 9;
    Nod* radacina = creareArbore(parinte, nr);
    coada = new Nod*[nr];
    afisareNivele(radacina);
    // (c)
    cout << "Persoane disponibilizate: ";
    afisareNoduriTerminale(radacina);
    cout << endl;
    // (d)
    if (esteAVL(radacina)) {
        cout << "Este avl"<< endl;
    } else {
        cout << "Nu este avl"<< endl;
    }
    return 0;
}