← Data structures from scratch · Lesson 18/32

Depth-first traversals

1/8

Three orders, one idea

Walking a tree depth-first (DFS) means going down one branch all the way before moving to the next. With recursion, at each node there are three things to do: visit the node, walk its left side and walk its right side. Depending on when you visit the node, you get a different order:

Preorder: node, left, right. Boss first, then the team.
Inorder: left, node, right.
Postorder: left, right, node. Children first, parent last.

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 preorden(n, r = []) {
25  if (!n) return r;
26  r.push(n.valor); preorden(n.izq, r); preorden(n.der, r);
27  return r;
28}
29function inorden(n, r = []) {
30  if (!n) return r;
31  inorden(n.izq, r); r.push(n.valor); inorden(n.der, r);
32  return r;
33}
34function postorden(n, r = []) {
35  if (!n) return r;
36  postorden(n.izq, r); postorden(n.der, r); r.push(n.valor);
37  return r;
38}
39
40const raiz = arbol([8, 3, 10, 1, 6, null, 14]);
41console.log("preorder: ", preorden(raiz));
42console.log("inorder:  ", inorden(raiz));
43console.log("postorder:", postorden(raiz));

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

const raiz = arbol([8, 3, 10, 1, 6, null, 14]);
console.log("preorder: ", preorden(raiz));
console.log("inorder:  ", inorden(raiz));
console.log("postorder:", postorden(raiz));

$ node leccion.js

Press RUN (or Ctrl+Enter).

What to look at

Preorder starts with the root (8) and postorder ends with it.
Inorder comes out sorted: 1, 3, 6, 8, 10, 14. Not by chance: in this tree everything left of each node is smaller and everything right is bigger. That's a search tree, the next unit.
The three functions are identical except for where the push goes.

The whole lesson on one page

Three orders, one idea

Preorder: node, left, right. Boss first, then the team.
Inorder: left, node, right.
Postorder: left, right, node. Children first, parent last.

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 preorden(n, r = []) {
25  if (!n) return r;
26  r.push(n.valor); preorden(n.izq, r); preorden(n.der, r);
27  return r;
28}
29function inorden(n, r = []) {
30  if (!n) return r;
31  inorden(n.izq, r); r.push(n.valor); inorden(n.der, r);
32  return r;
33}
34function postorden(n, r = []) {
35  if (!n) return r;
36  postorden(n.izq, r); postorden(n.der, r); r.push(n.valor);
37  return r;
38}
39
40const raiz = arbol([8, 3, 10, 1, 6, null, 14]);
41console.log("preorder: ", preorden(raiz));
42console.log("inorder:  ", inorden(raiz));
43console.log("postorder:", postorden(raiz));

Preorder starts with the root (8) and postorder ends with it.
Inorder comes out sorted: 1, 3, 6, 8, 10, 14. Not by chance: in this tree everything left of each node is smaller and everything right is bigger. That's a search tree, the next unit.
The three functions are identical except for where the push goes.

Height in one line

Many tree problems are solved with the same shape: "ask your left, ask your right, and combine". A tree's height (or maximum depth) is 1 plus the larger height of its two subtrees; an empty tree's is 0.

That's postorder: the node answers after hearing from its children. It's the "Maximum Depth of Binary Tree" 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 altura(nodo) {
25  if (nodo === null) return 0;
26  return 1 + Math.max(altura(nodo.izq), altura(nodo.der));
27}
28
29console.log(altura(arbol([8, 3, 10, 1, 6, null, 14])));
30console.log(altura(arbol([1, 2, null, 3, null, 4])));   // a stick leaning left
31console.log(altura(arbol([])));

3 for the usual tree; 4 for the stick (four nodes, one per level), and 0 for the empty one.

The mirror and the common ancestor

Inverting a tree (mirroring it) means swapping the two children of every node. Recursively: invert the left, invert the right and swap them. The mirror's inorder comes out exactly reversed.

The lowest common ancestor of two nodes is the deepest node that has both below it. Same shape: if the node is one of the two, it answers itself; otherwise it asks both sides. If both sides found something, the nodes are split up and the ancestor is this one.

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 inorden(n, r = []) {
25  if (n) { inorden(n.izq, r); r.push(n.valor); inorden(n.der, r); }
26  return r;
27}
28
29function invertir(nodo) {
30  if (nodo === null) return null;
31  const izq = invertir(nodo.izq);
32  const der = invertir(nodo.der);
33  nodo.izq = der;
34  nodo.der = izq;
35  return nodo;
36}
37
38function ancestro(nodo, p, q) {
39  if (nodo === null || nodo.valor === p || nodo.valor === q) return nodo;
40  const izq = ancestro(nodo.izq, p, q);
41  const der = ancestro(nodo.der, p, q);
42  if (izq && der) return nodo;      // one on each side: it's me
43  return izq ?? der;                // both on the same side
44}
45
46const raiz = arbol([3, 5, 1, 6, 2, 0, 8, null, null, 7, 4]);
47console.log("ancestor of 5 and 1:", ancestro(raiz, 5, 1).valor);
48console.log("ancestor of 7 and 4:", ancestro(raiz, 7, 4).valor);
49console.log("ancestor of 5 and 4:", ancestro(raiz, 5, 4).valor);
50
51console.log("before:", inorden(raiz));
52invertir(raiz);
53console.log("mirror:", inorden(raiz));

5 and 1 are on either side of the root: their ancestor is 3. 7 and 4 hang from 2.
For 5 and 4 you get 5: a node counts as its own ancestor, and 4 is below it.
The mirror's inorder is the previous one, read back to front.

Depth-first traversals

Three orders, one idea

Three orders, one idea

Height in one line

The mirror and the common ancestor

Practice with a video challenge

Further reading