Skip to content
Ayotl
Español

← Data structures from scratch · Lesson 17/32

Binary trees

✕
1/9

A tree, upside down

A linked list is a line of nodes where each one points to the next. In a tree, each node can point to several. In a binary tree, to two at most: its left child and its right child.

The vocabulary, with the drawing:

  • The root is the top node, the only one without a parent: 8.
  • The children of 3 are 1 and 6; 3 is their parent.
  • The leaves are nodes with no children: 1, 6 and 14.
  • A node's depth is how many steps it is from the root: 8 is at 0, 6 at 2.
  • The tree's height is how many levels it has: this one has 3.

They're drawn with the root on top, upside down from real trees. And they're everywhere: your computer's folders, a web page's HTML, a database index.

83101614
The whole lesson on one page

A tree, upside down

A linked list is a line of nodes where each one points to the next. In a tree, each node can point to several. In a binary tree, to two at most: its left child and its right child.

The vocabulary, with the drawing:

  • The root is the top node, the only one without a parent: 8.
  • The children of 3 are 1 and 6; 3 is their parent.
  • The leaves are nodes with no children: 1, 6 and 14.
  • A node's depth is how many steps it is from the root: 8 is at 0, 6 at 2.
  • The tree's height is how many levels it has: this one has 3.

They're drawn with the root on top, upside down from real trees. And they're everywhere: your computer's folders, a web page's HTML, a database index.

83101614

A node with two pointers

In code, a node is an object with its valor and two references, izq and der, which are null when there's no child. Just like in the values and references unit: the node doesn't contain its children, it points to them.

Below, the tree from the drawing is built by hand, from the inside out.

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

const raiz = new NodoArbol(8,
  new NodoArbol(3, new NodoArbol(1), new NodoArbol(6)),
  new NodoArbol(10, null, new NodoArbol(14)),
);

console.log(raiz.valor);
console.log(raiz.izq.valor, raiz.der.valor);
console.log(raiz.izq.der.valor);
console.log(raiz.der.izq);
console.log(raiz.izq);
  • The root is 8 and its children are 3 and 10.
  • raiz.izq.der is "the right child of the left child": 6.
  • 10 has no left child: null.
  • The last line shows node 3 whole, with its two children inside.

Building it by levels

Writing big trees by hand gets tiring. The LeetCode convention (also used in the video challenges) is writing them by levels, left to right, with null where a child is missing: the tree from the drawing is [8, 3, 10, 1, 6, null, 14].

The arbol function below does the conversion; you'll see it at the top of the other programs in this unit. And to walk it, the natural tool is recursion: a tree is a node with two smaller trees hanging from it. Counting nodes is "me, plus the ones on my left, plus the ones on my right".

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

function arbol(niveles) {
  if (!niveles.length || niveles[0] === null) return null;
  const raiz = new NodoArbol(niveles[0]);
  const cola = [raiz];
  let i = 1;
  while (i < niveles.length) {
    const nodo = cola.shift();
    if (niveles[i] != null) { nodo.izq = new NodoArbol(niveles[i]); cola.push(nodo.izq); }
    i++;
    if (i < niveles.length && niveles[i] != null) { nodo.der = new NodoArbol(niveles[i]); cola.push(nodo.der); }
    i++;
  }
  return raiz;
}

function contar(nodo) {
  if (nodo === null) return 0;          // empty tree
  return 1 + contar(nodo.izq) + contar(nodo.der);
}

// Sideways: root on the left, right children on top
function dibujar(nodo, sangria = "") {
  if (nodo === null) return;
  dibujar(nodo.der, sangria + "    ");
  console.log(sangria + nodo.valor);
  dibujar(nodo.izq, sangria + "    ");
}

const raiz = arbol([8, 3, 10, 1, 6, null, 14]);
console.log("nodes:", contar(raiz));
dibujar(raiz);
  • Six nodes: the nulls don't count.
  • The drawing comes out lying down: tilt your head left and it's the same tree as the first card, with 8 as the root.

Each node's depth

To find each node's depth, you walk down the tree passing a number along: the root gets 0 and each child gets one more than its parent. The tree's height is the largest depth, plus one.

Notice that the recursion visits the whole left branch first and then the right one: that's a depth-first traversal, the topic of the next lesson.

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

function arbol(niveles) {
  if (!niveles.length || niveles[0] === null) return null;
  const raiz = new NodoArbol(niveles[0]);
  const cola = [raiz];
  let i = 1;
  while (i < niveles.length) {
    const nodo = cola.shift();
    if (niveles[i] != null) { nodo.izq = new NodoArbol(niveles[i]); cola.push(nodo.izq); }
    i++;
    if (i < niveles.length && niveles[i] != null) { nodo.der = new NodoArbol(niveles[i]); cola.push(nodo.der); }
    i++;
  }
  return raiz;
}

let maxima = 0;
function profundidades(nodo, p) {
  if (nodo === null) return;
  console.log("  ".repeat(p) + nodo.valor + " is at depth " + p + (nodo.izq || nodo.der ? "" : " (leaf)"));
  maxima = Math.max(maxima, p);
  profundidades(nodo.izq, p + 1);
  profundidades(nodo.der, p + 1);
}

profundidades(arbol([8, 3, 10, 1, 6, null, 14]), 0);
console.log("height:", maxima + 1);

The three leaves (1, 6 and 14) are at depth 2, so the height is 3. The order they come out in (8, 3, 1, 6, 10, 14) goes down the left before going right.

Further reading