Tree Traversal

Introduzione

Gli tree traversal sono le tecniche utilizzate per visitare tutti i nodi di un albero in un ordine preciso. Solo dopo aver padroneggiato questi schemi è possibile:

• trovare un valore all’interno di un binary search tree
• convertire un albero in un array
• serializzare/deserializzare una struttura
• applicare algoritmi come sum, max depth, path sum

In questo capitolo distingueremo due macro famiglie:

1. Breadth First Search (BFS) – visita l’albero livello per livello usando una coda
2. Depth First Search (DFS) – scende in profondità (solitamente con recursion) e ha tre varianti principali: preorder, postorder, inorder

Terminologia rapida

• Visita: quando un nodo viene letto e aggiunto al risultato
• Queue: struttura FIFO usata dal BFS
• Call stack: struttura LIFO che supporta la recursion delle funzioni DFS
• Traversal order: la sequenza finale dei valori visitati

Breadth First Search (BFS)

Il BFS attraversa l’albero livello per livello. In pratica:

1. Mettiamo la root in una coda
2. Finché la coda non è vuota:
   • estraiamo il nodo in testa (shift)
   • salviamo il suo valore nel risultato
   • se esiste, aggiungiamo il figlio sinistro alla coda
   • se esiste, aggiungiamo il figlio destro alla coda

Visualizzazione passo-passo

Queue: [47]                  Result: []
Queue: [21, 76]              Result: [47]
Queue: [76, 18, 27]          Result: [47, 21]
Queue: [18, 27, 52, 82]      Result: [47, 21, 76]
Queue: [27, 52, 82]          Result: [47, 21, 76, 18]
...
Queue: []                    Result: [47, 21, 76, 18, 27, 52, 82]

Implementazione BFS

1
class BinarySearchTree {
2
  constructor() {
3
    this.root = null
4
  }
5

6
  breadthFirstSearch() {
7
    // Array che conterrà i valori visitati nell'ordine BFS
8
    const results = []
9
    // Queue per mantenere i nodi ancora da visitare
10
    const queue = []
11

12
    if (this.root) {
13
      queue.push(this.root)
14
    }
15

16
    while (queue.length) {
17
      // Il nodo corrente è sempre il primo in queue
18
      const current = queue.shift()
19

20
      // Visitiamo (push) il valore del nodo corrente
21
      results.push(current.value)
22

23
      // Aggiungiamo i figli alla queue per i livelli successivi
24
      if (current.left) queue.push(current.left)
25
      if (current.right) queue.push(current.right)
26
    }
27

28
    return results
29
  }
30
}

Quando usare BFS

• Quando serve conoscere il livello di un nodo (es. distanza minima dalla root)
• Per trovare il primo nodo che soddisfa una condizione in un albero bilanciato
• Per convertire l’albero in un array level-order (utile nella serializzazione)

Depth First Search (DFS)

Il DFS percorre l’albero andando il più in profondità possibile prima di tornare indietro. Si appoggia quasi sempre alla recursion.

DFS vs BFS: panoramica rapida

Pattern ricorsivo tipico

1
function traverse(node) {
2
  if (!node) return
3
  // ...logica specifica della variante DFS...
4
}
5

6
traverse(this.root)

DFS Preorder

Ordine: root → left → right. Ottimo per copiare un albero o serializzarlo.

1
class BinarySearchTree {
2
  dfsPreorder() {
3
    const results = []
4

5
    function traverse(node) {
6
      if (!node) return
7
      results.push(node.value)      // Visita durante la discesa
8
      traverse(node.left)           // Vai a sinistra
9
      traverse(node.right)          // Poi a destra
10
    }
11

12
    traverse(this.root)
13
    return results
14
  }
15
}

DFS Postorder

Ordine: left → right → root. Utile quando bisogna cancellare nodi o calcolare attributi cumulativi (es. altezza).

1
class BinarySearchTree {
2
  dfsPostorder() {
3
    const results = []
4

5
    function traverse(node) {
6
      if (!node) return
7
      traverse(node.left)           // visita sotto-albero sinistro
8
      traverse(node.right)          // poi quello destro
9
      results.push(node.value)      // visita solo alla risalita
10
    }
11

12
    traverse(this.root)
13
    return results
14
  }
15
}

DFS Inorder

Ordine: left → root → right. Su un Binary Search Tree restituisce i valori in ordine crescente.

1
class BinarySearchTree {
2
  dfsInorder() {
3
    const results = []
4

5
    function traverse(node) {
6
      if (!node) return
7
      traverse(node.left)
8
      results.push(node.value)      // Visita tra sinistra e destra
9
      traverse(node.right)
10
    }
11

12
    traverse(this.root)
13
    return results
14
  }
15
}

Comparazione delle varianti DFS

Complessità

Quando scegliere BFS o DFS

Suggerimenti pratici

1. BFS → Queue: inizializza sempre la coda con la root (se esiste) prima del loop
2. DFS ricorsivi → base case: ritorna immediatamente quando node === null
3. Ordine coerente: per gli alberi binari usa sempre “sinistra prima di destra” per evitare ambiguità
4. Debug: stampa il call stack con console.log('enter', node.value) e console.log('exit', node.value) per capire la sequenza