Sommare i Valori di un Albero Binario in JavaScript senza Cicli: La mia Soluzione al XtremeJS Hackathon 2024

Durante l’XtremeJS Hackathon 2024, mi è stata posta questa sfida, apparentemente semplice ma con una particolarità interessante: niente cicli, solo ricorsione! Questo problema è un’ottima occasione per applicare un approccio funzionale a JavaScript, sfruttando la ricorsione per navigare l’albero binario.

Domanda: Scrivi una funzione in JavaScript che prenda la radice di un albero binario, in cui ciascun nodo contenga un numero, e restituisca la somma totale di tutti i numeri contenuti nei nodi. Non è ammesso usare cicli, solo la ricorsione è ammessa.

In questo articolo ti guiderò attraverso la mia soluzione. Alla fine, avremo una funzione sumTree che, data la radice di un albero binario, calcola la somma totale dei nodi ricorsivamente. Per semplificare l’implementazione e migliorare la leggibilità, ho anche aggiunto una funzione helper createNode.

Step 1: Definire la Classe `Node`

La prima cosa da fare è definire una classe Node, che rappresenta ogni nodo dell'albero binario. Ogni nodo ha:

un valore numerico value,
un figlio sinistro left,
un figlio destro right.

Ecco come appare in JavaScript:

class Node {
    constructor(value, left = null, right = null) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}

Step 2: La Funzione Ricorsiva `sumTree`

La funzione sumTree è dove avviene la logica per calcolare la somma. Il funzionamento è semplice:

Caso Base: Se root è null, restituisce 0, poiché non ci sono valori da aggiungere.
Caso Ricorsivo: Se root non è null, somma il valore del nodo (root.value) alla somma del sottoramo sinistro (sumTree(root.left)) e alla somma del sottoramo destro (sumTree(root.right)).

Ecco il codice:

function sumTree(root) {
    return root ? root.value + sumTree(root.left) + sumTree(root.right) : 0;
}

Step 3: La Funzione Helper `createNode`

Per costruire l’albero in modo più leggibile, ho creato una funzione helper createNode che restituisce un nuovo nodo Node. In questo modo, possiamo creare l’albero in modo più intuitivo e pulito.

function createNode(value, left = null, right = null) {
    return new Node(value, left, right);
}

Esempio Completo e Funzionante

Supponiamo di voler creare il seguente albero binario:


       10
      /   \
     6     15
    / \    / \
   3   8  12  20

Il codice completo per costruire e sommare i valori di questo albero binario è il seguente:

class Node {
    constructor(value, left = null, right = null) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}

function sumTree(root) {
    return root ? root.value + sumTree(root.left) + sumTree(root.right) : 0;
}

function createNode(value, left = null, right = null) {
    return new Node(value, left, right);
}

// Esempio di utilizzo
const root = createNode(
    10,
    createNode(6, createNode(3), createNode(8)),
    createNode(15, createNode(12), createNode(20))
);

console.log(sumTree(root)); // Output atteso: 74

Risultato

Quando eseguiamo sumTree(root), otteniamo 74, la somma di tutti i valori dei nodi dell’albero binario.

Conclusione

Questa sfida per l’XtremeJS Hackathon è stata un'ottima occasione per lavorare con strutture dati e la ricorsione in JavaScript. La soluzione, senza utilizzare cicli, è efficiente e ben strutturata, sfruttando la semplicità della ricorsione per navigare l'albero binario.

Se vuoi migliorare le tue abilità in JavaScript e metodi ricorsivi, questa è un’ottima esercitazione. Buona programmazione e… alla prossima sfida!

Step 1: Definire la Classe Node

Step 2: La Funzione Ricorsiva sumTree