# :christmas_tree: Alberi
Albero Binario:

typedef struct TreeNode {
    int data;
    struct TreeNode * left;
    struct TreeNode * right;
} TreeNode;
typedef TreeNode * Tree;

---

# Numero di Foglie
Si scriva una funzione che, dato un albero binario, conti il numero delle foglie dell’albero.

int contaFoglie(Tree root){
	// Caso base: albero vuoto
	if(root == NULL) return 0;
	
	// Caso base: siamo arrivati a una foglia
	if(root->right == NULL && root->left == NULL) return 1;
	
	// Caso ricorsivo: non sono una foglia
	return contaFoglie(root->right) + contaFoglie(root->left);
}

---

# Numero di Branches (non foglie)
Si scriva una funzione che conta il numero di nodi che non sono foglie.

int contaNoFoglie(Tree root){
    // Se root è una foglia non conta niente
    if(root == NULL || (root->right == NULL && root->left == NULL)) return 0;
    
    // Se root non è una foglia conta 1
    return 1 + contaNoFoglie(root->left) + contaNoFoglie(root->right);
}

---

# Somma Nodi
Si scriva una funzione che restituisce la somma di tutti i nodi dell’albero.

// Sommare il valore dei nodi
int sommaNodi(Tree root){
    // Caso Base: albero vuoto
    if(root == NULL) return 0;

    // Caso Ricorsivo
    int value = root->data;
    int value_left = sommaNodi(root->left);
    int value_right = sommaNodi(root->right);

    return value + value_left + value_right;
}

---

# Inserimento Ordinato (per BST)
Si scriva una funzione che, dato un albero BST e un valore, inserisce un nuovo nodo nell'albero (senza ripetizioni).

Tree createNode(int value) {
    Tree newNode = (Tree)malloc(sizeof(TreeNode));
    if (newNode == NULL) {
        printf("Errore di allocazione memoria.\n");
        return NULL;
    }
    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

Tree insert(Tree root, int value) {
    if (root == NULL) {
        return createNode(value); // Crea un nuovo nodo se il sottoalbero è vuoto
    }

    if (value < root->data) {
        root->left = insert(root->left, value); // Inserisce a sinistra
    } else if (value > root->data) {
        root->right = insert(root->right, value); // Inserisce a destra
    }
    // Se il valore è già presente, non fare nulla (niente duplicati)
    return root;
}

---

# Cerca Max
Si scriva una funzione che restituisce il massimo valore di un nodo contenuto in un albero.
Si implementino due funzioni, una che opera per alberi generici e una che opera per Alberi Binari di Ricerca (BST).

## Versione per Alberi Generici

int max2(int a, int b){
    if(a > b) return a;
    else return b;
}

int max3(int a, int b, int c){
    return max2(a, max2(b, c));
}

int cercaMax(Tree root){
    // Caso Albero Vuoto (ci entro solo se l'albero di partenza è vuoto)
    // Oppure se un nodo non foglia ha un solo figlio
    if(root == NULL) return 0;

    // Caso Foglia
    if(root->left == NULL && root->right == NULL) return root->data;

    // Caso Ricorsivo
    int value = root->data;
    int max_left = cercaMax(root->left, err);
    int max_right = cercaMax(root->right, err);

    return max3(value, max_left, max_right);
}

## Versione per BST

int cercaMaxOrdinato(Tree root){
	if(root == NULL) return 0;
	
	if(root->right == NULL) return root->data;
	
	return cercaMaxOrdinato(root->right, err);
}

==**Nota:** come si gestisce il caso in cui l'albero di partenza è vuoto?==

---

# Alberi Identici
Scrivere una funzione che prende in inout due alberi e restituisce 1 se i due sono identici

int alberiIdentici(Tree root1, Tree root2){
    // Casi base
    if(root1 == NULL && root2 == NULL) return 1;
    if(root1 == NULL || root2 == NULL) return 0;

    // Casi ricorsivi
    int condizione_nodo = root1->data == root2->data;
    int condizione_left = alberiIdentici(root1->left, root2->left);
    int condizione_right = alberiIdentici(root1->right, root2->right);

    return condizione_nodo && condizione_left && condizione_right;
}

---

# Somma Nodi Contenuta in un Altro Albero
Dati due alberi binari, scrivere una funzione che restituisce 1 se la somma di tutti i nodi foglia di uno è uguale al valore di uno dei nodi dell’altro, o viceversa.

// Funzione per calcolare la somma dei nodi foglia di un albero
int sommaFoglie(Tree root) {
    // Caso base: albero vuoto
    if (root == NULL) return 0;

    // Caso foglia: aggiungo il valore alla somma
    if (root->left == NULL && root->right == NULL) return root->data;

    // Sommo ricorsivamente le foglie dei sottoalberi
    return sommaFoglie(root->left) + sommaFoglie(root->right);
}

// Funzione per verificare se un valore è presente come nodo in un albero
int trovaNodo(Tree root, int value) {
    // Caso base: albero vuoto
    if (root == NULL) return 0;

    // Se trovo il valore, restituisco 1
    if (root->data == value) return 1;

    // Cerco ricorsivamente nei sottoalberi
    return trovaNodo(root->left, value) || trovaNodo(root->right, value);
}

// Funzione principale per verificare la condizione
int verificaSommaUgualeNodo(Tree root1, Tree root2) {
    // Calcolo la somma dei nodi foglia del primo albero
    int somma_foglie1 = sommaFoglie(root1);

    // Controllo se la somma dei nodi foglia del primo albero
    // corrisponde a uno dei nodi del secondo albero
    if (trovaNodo(root2, somma_foglie1)) {
        return 1;
    }

    // Calcolo la somma dei nodi foglia del secondo albero
    int somma_foglie2 = sommaFoglie(root2);

    // Controllo se la somma dei nodi foglia del secondo albero
    // corrisponde a uno dei nodi del primo albero
    if (trovaNodo(root1, somma_foglie2)) {
        return 1;
    }

    return 0;
}

---

# Numero di Elementi Uguali
Si scriva una funzione che, dato un albero e un intero k, restituisce 1 se l’albero ha esattamente k elementi uguali tra loro.
Si implementino due versioni, una senza utilizzare strutture ausiliarie e un'altra che utlizzi delle strutture ausiliarie.

## Soluzione SENZA Strutture Ausiliarie

// Funzioni
int contaOccorrenze(Tree root, int value) {
    // Caso base: albero vuoto
    if (root == NULL) return 0;

    // Conta il nodo corrente se il valore coincide
    int count = 0;
    if(root->data == value) count = 1;

    // Somma le occorrenze nei sottoalberi
    return count + contaOccorrenze(root->left, value) + contaOccorrenze(root->right, value);
}

int verificaKElementi(Tree current_root, int k, Tree original_root) {
    // Caso base: albero vuoto
    if (current_root == NULL) return 0;

    // Conta quante volte il valore del nodo corrente appare nell'albero
    int occorrenze = contaOccorrenze(original_root, current_root->data);

    // Se il valore appare esattamente k volte, restituisco 1
    if (occorrenze == k) return 1;

    // Altrimenti, continuo a verificare nei sottoalberi
    // Nota: ignoro i nodi già verificati
    int res_sx = verificaKElementi(current_root->left, k, original_root);
    int res_dx = verificaKElementi(current_root->right, k, original_root);

    return res_sx || res_dx;
}

==:warning: La soluzione presentata a lezione, come fatto notare da due vostri colleghi, non analizzava un caso chiave, ovvero quando i nodi sono frammentati in due sottoalberi diversi. La soluzione presentata riportata qui, invece, risolve il problema contando le occorrenze a partire sempre dalla radice originale. Per fare ciò, bisogna passare tra una chiamata e l'altra la radice originale.==

## Soluzione con Struttura di Appoggio
Uso una lista compressa ausiliaria:

// Nodo per la lista di conteggio
typedef struct CountNode {
    int value;
    int count;
    struct CountNode *next;
} CountNode;
typedef CountNode *pCountNode;

Con le seguenti funzioni di gestione:

pCountNode aggiornaLista(pCountNode head, int value) {
    pCountNode curr = head;

    // Cerca il valore nella lista
    while (curr != NULL) {
        if (curr->value == value) {
            curr->count++;
            return head; // Aggiornato
        }
        curr = curr->next;
    }

    // Valore non trovato, aggiungi nuovo nodo
    pCountNode new_node = (pCountNode)malloc(sizeof(CountNode));
    if (new_node == NULL) {
        printf("Errore di allocazione.\n");
        return head;
    }
    new_node->value = value;
    new_node->count = 1;
    new_node->next = head;

    return new_node;
}

void liberaLista(pCountNode head) {
    pCountNode curr;
    while (head != NULL) {
        curr = head;
        head = head->next;
        free(curr);
    }
}

int verificaKOccorrenze(pCountNode head, int k) {
    pCountNode curr = head;
    while (curr != NULL) {
        if (curr->count == k) {
            return 1; // Trovato
        }
        curr = curr->next;
    }
    return 0; // Non trovato
}

La soluzione salva i nodi dell’albero all’interno della lista compressa che viene popolata con la ricorsione, la lista quindi avrà in ogni nodo un valore associato a quante volte appare nell'albero.

pCountNode popolaLista(Tree root, pCountNode head) {
    // Albero vuoto
    if (root == NULL) return head;

    // Aggiorna con il nodo corrente
    head = aggiornaLista(head, root->data);

    // Scorro i sottoalberi
    head = popolaLista(root->left, head);
    head = popolaLista(root->right, head);

    return head;
}

int verificaKElementi(Tree root, int k){
	// Popolo la lista
	pCountNode head = NULL;
	head = popolaLista(root, head);
	
	// Verifico che ci siano k elementi uguali
	int res = verificaKOccorrenze(head, k);
	
	// Svuoto la lista
	liberaLista(head);
	
	return res;
}

---

# Albero Isobato

Si scriva una funzione che prende in input un albero e restituisce 1 se l’albero è isobato, 0 altrimenti.

Un albero si dice isobato se tutti i cammini dalla radice alle foglie hanno la stessa lunghezza.

## Soluzione 1

// Funzione per calcolare il cammino di lunghezza massima
int maxDepth(Tree root){
    if(root == NULL) return 0;

    int depth_sx, depth_dx;
    depth_sx = maxDepth(root->left);
    depth_dx = maxDepth(root->right);
    
    if(depth_sx > depth_dx) return depth_sx + 1;
    else return depth_dx + 1;
}
// Funzione per calcolare il cammino di lunghezza minima
int minDepth(Tree root){
    if(root == NULL) return 0;

    int depth_sx, depth_dx;
    depth_sx = minDepth(root->left);
    depth_dx = minDepth(root->right);

    if(depth_sx == 0) return depth_dx + 1;
    if(depth_dx == 0) return depth_sx + 1;
    
    if(depth_sx < depth_dx) return depth_sx + 1;
    else return depth_dx + 1;
}

int alberoIsobato(Tree root){
    return maxDepth(root) == minDepth(root);
}

==**Nota:** le righe 20 e 21 servono a gestire correttamente il caso in cui un nodo ha un solo figlio, altrimenti si restituisce al chiamante la `min_depth` sbagliata. Ad esempio, nel caso cerchiato nella figura sottostante, si restituisce correttamente al chiamante 2, altrimenti si restituirebbe 1.==


## Soluzione 2

// Funzione ausiliaria per calcolare la profondità e verificare l'isobatia
int verificaProfondita(Tree root, int *isIsobato) {
    // Caso base: albero vuoto
    if (root == NULL) return 0;

    // Calcolo ricorsivo della profondità dei sottoalberi
    int profondita_sx = verificaProfondita(root->left, isIsobato);
    int profondita_dx = verificaProfondita(root->right, isIsobato);

    // Verifica se i sottoalberi hanno la stessa profondità
    if (profondita_sx != profondita_dx) {
        *isIsobato = 0; // Non è isobato
    }

    // Restituisce la profondità attuale del sottoalbero
		int profondita_corrente;
		if (profondita_sx > profondita_dx) {
		    profondita_corrente = profondita_sx;
		} else {
		    profondita_corrente = profondita_dx;
		}
		return profondita_corrente + 1;
}
    
int alberoIsobato(Tree root) {
    // Variabile per tracciare se l'albero è isobato
    int isIsobato = 1;
    verificaProfondita(root, &isIsobato);
    return isIsobato;
}

---

# Alberi Ternari Isobati

Scrivere una funzione che dice se un albero ternario è isobato oppure no.

Si consideri la seguente definizione:

typedef struct NodeTree {
    int data;
    struct NodeTree * left;
    struct NodeTree * right;
    struct NodeTree * center;
} NodeTree; 
typedef NodeTree * Tree;

// Funzione ausiliaria
int verificaIsobato(Tree root, int profondita_corrente, int *profondita_foglia) {
    // Caso base: nodo vuoto
    if (root == NULL) {
        return 1; // Nodo vuoto non influisce sull'isobatia
    }

    // Caso base: foglia
    if (root->left == NULL && root->right == NULL && root->center == NULL) {
        // Se è la prima foglia incontrata, salvo la profondità
        if (*profondita_foglia == -1) {
            *profondita_foglia = profondita_corrente;
            return 1; // Fin qui l'albero è isobato
        }
        // Controllo che la profondità della foglia corrente sia uguale alla profondità salvata
        return *profondita_foglia == profondita_corrente;
    }

    // Caso ricorsivo
    int is_left_isobato = verificaIsobato(root->left, profondita_corrente + 1, profondita_foglia);
    int is_right_isobato = verificaIsobato(root->right, profondita_corrente + 1, profondita_foglia);
    int is_center_isobato = verificaIsobato(root->center, profondita_corrente + 1, profondita_foglia);

    return is_left_isobato && is_right_isobato && is_center_isobato;
}

// Funzione principale
int alberoIsobato(Tree root) {
    int profondita_foglia = -1; // Per salvare la profondità della prima foglia incontrata
    return verificaIsobato(root, 0, &profondita_foglia);
}

---
# Alberi Artussiani

Si scriva una funzione che prende in input un albero e restituisce 1 se tale albero è artussiano.

Un albero si dice artussiano se e solo se è composto da:

- nodi foglia
- nodi con un solo figlio
- nodi con due figli aventi lo stesso numero di discendenti



## Soluzione 1

int contaNodi(Tree root){
	if(root == NULL) return 0;
	return contaNodi(root->left) + contaNodi(root->right) + 1;
}

int alberoArtussiano(Tree root){
	// Caso base: albero vuoto
	if(root == NULL) return 1;

	// Caso base: foglia
	if(root->left == NULL && root->right == NULL) return 1;
	
	// Analizzo il branch di destra
	if(root->left == NULL) return alberoArtussiano(root->right);
	
	// Oppure analizzo il branch di sinistra
	if(root->right == NULL) return alberoArtussiano(root->left);
	
	// Se ho entrambi i branch disponibili, devo verificare che:
	// Entrambi i branch hanno gli stessi nodi
	// Entrambi i sottoalberi sono artussiani
	if(contaNodi(root->left) == contaNodi(root->right) && alberoArtussiano(root->left) && alberoArtussiano(root->right)) return 1;
	
	return 0;
}

## Soluzione 2

// Funzione helper per calcolare numero di nodi e verificare se l'albero è artussiano
int alberoArtussianoHelper(Tree root, int *nodi) {
    // Caso base: albero vuoto
    if (root == NULL) {
        *nodi = 0;
        return 1;
    }

    // Variabili per il conteggio dei nodi dei sottoalberi
    int nodi_sx = 0, nodi_dx = 0;

    // Verifica se i sottoalberi sono artussiani
    int sx_artussiano = alberoArtussianoHelper(root->left, &nodi_sx);
    int dx_artussiano = alberoArtussianoHelper(root->right, &nodi_dx);

    // Calcola il numero di nodi totali
    *nodi = nodi_sx + nodi_dx + 1;

    // Verifica la condizione artussiana
    return sx_artussiano && dx_artussiano && (nodi_sx == nodi_dx);
}

// Funzione principale
int alberoArtussiano(Tree root) {
    int nodi = 0;
    return alberoArtussianoHelper(root, &nodi);
}