← Data structures from scratch · Lesson 19/32

Level-order traversal

1/8

Floor by floor, with a queue

Depth-first goes to the bottom of a branch. Level-order traversal (BFS, breadth-first search) does the opposite: the root first, then all its children, then all the grandchildren.

It isn't done with recursion but with a queue: put the root in; while the queue isn't empty, take the one at the front, visit it and line its children up at the back. Since a queue is first in, first out, everyone on one floor always comes out before anyone on the next.

leccion.js

1class NodoArbol {
2  constructor(valor, izq = null, der = null) {
3    this.valor = valor;
4    this.izq = izq;
5    this.der = der;
6  }
7}
8
9function arbol(niveles) {
10  if (!niveles.length || niveles[0] === null) return null;
11  const raiz = new NodoArbol(niveles[0]);
12  const cola = [raiz];
13  let i = 1;
14  while (i < niveles.length) {
15    const nodo = cola.shift();
16    if (niveles[i] != null) { nodo.izq = new NodoArbol(niveles[i]); cola.push(nodo.izq); }
17    i++;
18    if (i < niveles.length && niveles[i] != null) { nodo.der = new NodoArbol(niveles[i]); cola.push(nodo.der); }
19    i++;
20  }
21  return raiz;
22}
23
24function porAnchura(raiz) {
25  if (raiz === null) return;
26  const cola = [raiz];
27  while (cola.length > 0) {
28    const nodo = cola.shift();                    // the front one leaves
29    if (nodo.izq) cola.push(nodo.izq);            // its children go to the back
30    if (nodo.der) cola.push(nodo.der);
31    console.log("visit", nodo.valor, "| queue now:", cola.map((n) => n.valor));
32  }
33}
34
35porAnchura(arbol([3, 9, 20, null, null, 15, 7]));

class NodoArbol {
  constructor(valor, izq = null, der = null) {
    this.valor = valor;
    this.izq = izq;
    this.der = der;
  }
}

function porAnchura(raiz) {
  if (raiz === null) return;
  const cola = [raiz];
  while (cola.length > 0) {
    const nodo = cola.shift();                    // the front one leaves
    if (nodo.izq) cola.push(nodo.izq);            // its children go to the back
    if (nodo.der) cola.push(nodo.der);
    console.log("visit", nodo.valor, "| queue now:", cola.map((n) => n.valor));
  }
}

porAnchura(arbol([3, 9, 20, null, null, 15, 7]));

$ node leccion.js

Press RUN (or Ctrl+Enter).

What to look at

The order is 3, 9, 20, 15, 7: floor by floor, left to right. Look at the queue after visiting 20: its children, 15 and 7, lined up at the back and come out in the next two rounds.

The whole lesson on one page

Floor by floor, with a queue

Depth-first goes to the bottom of a branch. Level-order traversal (BFS, breadth-first search) does the opposite: the root first, then all its children, then all the grandchildren.

1class NodoArbol {
2  constructor(valor, izq = null, der = null) {
3    this.valor = valor;
4    this.izq = izq;
5    this.der = der;
6  }
7}
8
9function arbol(niveles) {
10  if (!niveles.length || niveles[0] === null) return null;
11  const raiz = new NodoArbol(niveles[0]);
12  const cola = [raiz];
13  let i = 1;
14  while (i < niveles.length) {
15    const nodo = cola.shift();
16    if (niveles[i] != null) { nodo.izq = new NodoArbol(niveles[i]); cola.push(nodo.izq); }
17    i++;
18    if (i < niveles.length && niveles[i] != null) { nodo.der = new NodoArbol(niveles[i]); cola.push(nodo.der); }
19    i++;
20  }
21  return raiz;
22}
23
24function porAnchura(raiz) {
25  if (raiz === null) return;
26  const cola = [raiz];
27  while (cola.length > 0) {
28    const nodo = cola.shift();                    // the front one leaves
29    if (nodo.izq) cola.push(nodo.izq);            // its children go to the back
30    if (nodo.der) cola.push(nodo.der);
31    console.log("visit", nodo.valor, "| queue now:", cola.map((n) => n.valor));
32  }
33}
34
35porAnchura(arbol([3, 9, 20, null, null, 15, 7]));

The order is 3, 9, 20, 15, 7: floor by floor, left to right. Look at the queue after visiting 20: its children, 15 and 7, lined up at the back and come out in the next two rounds.

Each level in its own array

Sometimes the order isn't enough: you want to know where each floor ends. The trick is to check how many are in the queue when a round starts: those are exactly the current level. Take out those tam, collect them in an array, and the children queued meanwhile are the next level.

That gives [[3], [9, 20], [15, 7]], which is the "Binary Tree Level Order Traversal" challenge.

1class NodoArbol {
2  constructor(valor, izq = null, der = null) {
3    this.valor = valor;
4    this.izq = izq;
5    this.der = der;
6  }
7}
8
9function arbol(niveles) {
10  if (!niveles.length || niveles[0] === null) return null;
11  const raiz = new NodoArbol(niveles[0]);
12  const cola = [raiz];
13  let i = 1;
14  while (i < niveles.length) {
15    const nodo = cola.shift();
16    if (niveles[i] != null) { nodo.izq = new NodoArbol(niveles[i]); cola.push(nodo.izq); }
17    i++;
18    if (i < niveles.length && niveles[i] != null) { nodo.der = new NodoArbol(niveles[i]); cola.push(nodo.der); }
19    i++;
20  }
21  return raiz;
22}
23
24function niveles(raiz) {
25  const r = [];
26  if (raiz === null) return r;
27  const cola = [raiz];
28  while (cola.length > 0) {
29    const tam = cola.length;        // the ones on this level
30    const nivel = [];
31    for (let i = 0; i < tam; i++) {
32      const nodo = cola.shift();
33      nivel.push(nodo.valor);
34      if (nodo.izq) cola.push(nodo.izq);
35      if (nodo.der) cola.push(nodo.der);
36    }
37    r.push(nivel);
38  }
39  return r;
40}
41
42console.log(niveles(arbol([3, 9, 20, null, null, 15, 7])));
43console.log(niveles(arbol([8, 3, 10, 1, 6, null, 14])));

One array per floor. The number of arrays is the tree's height, and the longest one tells you the widest floor.

What you see from the right

With the levels separated, problems that would be messy depth-first come out easily. If you stand to the right of the tree, on each floor you only see the last node: the "right side view" is the last of each level.

A note on cost: shift() on an array is O(n), because it moves everything to close the gap (you saw this in the queues unit). For small trees it doesn't matter; for millions of nodes, use the queue with a front index.

1class NodoArbol {
2  constructor(valor, izq = null, der = null) {
3    this.valor = valor;
4    this.izq = izq;
5    this.der = der;
6  }
7}
8
9function arbol(niveles) {
10  if (!niveles.length || niveles[0] === null) return null;
11  const raiz = new NodoArbol(niveles[0]);
12  const cola = [raiz];
13  let i = 1;
14  while (i < niveles.length) {
15    const nodo = cola.shift();
16    if (niveles[i] != null) { nodo.izq = new NodoArbol(niveles[i]); cola.push(nodo.izq); }
17    i++;
18    if (i < niveles.length && niveles[i] != null) { nodo.der = new NodoArbol(niveles[i]); cola.push(nodo.der); }
19    i++;
20  }
21  return raiz;
22}
23
24function vistaDerecha(raiz) {
25  const r = [];
26  const cola = raiz ? [raiz] : [];
27  let frente = 0;                   // instead of shift(): an index
28  while (frente < cola.length) {
29    const fin = cola.length;        // the level runs from frente to fin
30    for (let i = frente; i < fin; i++) {
31      const nodo = cola[i];
32      if (i === fin - 1) r.push(nodo.valor);   // last one on the floor
33      if (nodo.izq) cola.push(nodo.izq);
34      if (nodo.der) cola.push(nodo.der);
35    }
36    frente = fin;
37  }
38  return r;
39}
40
41console.log(vistaDerecha(arbol([1, 2, 3, null, 5, null, 4])));
42console.log(vistaDerecha(arbol([1, 2, 3, 4])));

First tree: 1, 3 and 4, the ones on the right edge.
Second: 1, 3 and 4, even though 4 hangs on the left side: on its floor there's nobody further right to hide it.

Practice with a video challenge

Binary Tree Level Order Traversal

Level-order traversal

Floor by floor, with a queue

Floor by floor, with a queue

Each level in its own array

What you see from the right

Practice with a video challenge

Further reading