Skip to content
Ayotl
Español

← Data structures from scratch · Lesson 20/32

Searching and inserting in a BST

✕
1/8

A single rule

A binary search tree (BST) is a binary tree with one rule: at every node, everything hanging to its left is smaller and everything hanging to its right is bigger. Not just its direct children: the whole subtree.

To insert, you don't have to think about where: compare with the root and go left or right until you hit a gap (null). That's where the new node hangs. If the value was already there, here it's ignored.

The drawing is the tree you get by inserting 8, 3, 10, 1, 6, 14, 4 and 7, in that order.

8310161447
leccion.js

$ node leccion.js

Press RUN (or Ctrl+Enter).

What to look at

  • The root is 8, the first one in; 3 is on its left and 10 on its right.
  • 6 ended up to the right of 3 (it's bigger than 3) but to the left of 8 (it's smaller than 8).
  • 4 and 7 hang from 6. Change the order of the list and run it: the same values give a different tree.
The whole lesson on one page

A single rule

A binary search tree (BST) is a binary tree with one rule: at every node, everything hanging to its left is smaller and everything hanging to its right is bigger. Not just its direct children: the whole subtree.

To insert, you don't have to think about where: compare with the root and go left or right until you hit a gap (null). That's where the new node hangs. If the value was already there, here it's ignored.

The drawing is the tree you get by inserting 8, 3, 10, 1, 6, 14, 4 and 7, in that order.

8310161447
class Nodo {
  constructor(valor) {
    this.valor = valor;
    this.izq = null;   // smaller
    this.der = null;   // bigger
  }
}

function insertar(raiz, valor) {
  if (raiz === null) return new Nodo(valor);   // the gap: it goes here
  if (valor < raiz.valor) raiz.izq = insertar(raiz.izq, valor);
  else if (valor > raiz.valor) raiz.der = insertar(raiz.der, valor);
  return raiz;   // duplicates are ignored
}

let raiz = null;
for (const v of [8, 3, 10, 1, 6, 14, 4, 7]) raiz = insertar(raiz, v);

console.log(raiz.valor, raiz.izq.valor, raiz.der.valor);
console.log(raiz.izq.der.valor);
console.log(raiz.izq.der.izq.valor, raiz.izq.der.der.valor);
  • The root is 8, the first one in; 3 is on its left and 10 on its right.
  • 6 ended up to the right of 3 (it's bigger than 3) but to the left of 8 (it's smaller than 8).
  • 4 and 7 hang from 6. Change the order of the list and run it: the same values give a different tree.

Searching means going down one side

Searching works just like inserting: compare and go down. Each comparison discards a whole subtree, so the steps don't depend on how many nodes there are, but on the tree's height, h. Searching and inserting cost O(h).

If the tree is well spread out, the height is roughly log₂ n and searching is as fast as binary search on a sorted array. The difference: here adding a new value is also O(h), while in the array you had to shift everything to make room.

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

function insertar(raiz, valor) {
  if (raiz === null) return new Nodo(valor);
  if (valor < raiz.valor) raiz.izq = insertar(raiz.izq, valor);
  else if (valor > raiz.valor) raiz.der = insertar(raiz.der, valor);
  return raiz;
}

function armar(valores) {
  let raiz = null;
  for (const v of valores) raiz = insertar(raiz, v);
  return raiz;
}

// Returns how many nodes it visited; negative if not found
function buscar(raiz, valor) {
  let nodo = raiz, pasos = 0;
  while (nodo !== null) {
    pasos++;
    if (valor === nodo.valor) return pasos;
    nodo = valor < nodo.valor ? nodo.izq : nodo.der;
  }
  return -pasos;
}

const raiz = armar([8, 3, 10, 1, 6, 14, 4, 7]);
console.log("7:", buscar(raiz, 7));
console.log("14:", buscar(raiz, 14));
console.log("8:", buscar(raiz, 8));
console.log("5:", buscar(raiz, 5));
  • 7 is 4 steps away: 8 → 3 → 6 → 7.
  • 8 is 1 step away: it's the root.
  • 5 isn't there: it found out in 4 steps (8 → 3 → 6 → 4 and then null), without ever looking at 10 or 14.

In-order comes out sorted, and the validation trap

If you walk the tree in order (left first, then the node, then the right), the values come out sorted from smallest to largest. That's proof the rule holds.

And a classic interview trap: to check whether a tree is a BST, comparing each node with its children isn't enough. In the drawing's tree, 6 is bigger than its parent 3 (fine), but it sits to the left of 5 and is bigger than 5 (wrong). You have to go down carrying the limits each node must respect.

536
class Nodo {
  constructor(valor) {
    this.valor = valor;
    this.izq = null;
    this.der = null;
  }
}

function insertar(raiz, valor) {
  if (raiz === null) return new Nodo(valor);
  if (valor < raiz.valor) raiz.izq = insertar(raiz.izq, valor);
  else if (valor > raiz.valor) raiz.der = insertar(raiz.der, valor);
  return raiz;
}

function armar(valores) {
  let raiz = null;
  for (const v of valores) raiz = insertar(raiz, v);
  return raiz;
}

function inorden(nodo, salida = []) {
  if (nodo === null) return salida;
  inorden(nodo.izq, salida);
  salida.push(nodo.valor);
  inorden(nodo.der, salida);
  return salida;
}

function esBST(nodo, min = -Infinity, max = Infinity) {
  if (nodo === null) return true;
  if (nodo.valor <= min || nodo.valor >= max) return false;
  // on the left, this value is the ceiling; on the right, the floor
  return esBST(nodo.izq, min, nodo.valor) && esBST(nodo.der, nodo.valor, max);
}

const raiz = armar([8, 3, 10, 1, 6, 14, 4, 7]);
console.log(inorden(raiz));
console.log(esBST(raiz));

// Built by hand to be wrong: 6 to the left of 5
const malo = new Nodo(5);
malo.izq = new Nodo(3);
malo.izq.der = new Nodo(6);
console.log(inorden(malo));
console.log(esBST(malo));
  • The good tree comes out [1, 3, 4, 6, 7, 8, 10, 14]: sorted.
  • The bad one comes out [3, 6, 5]: 6 before 5 gives it away, and esBST catches it because 6 arrived with a ceiling of 5.

Practice with a video challenge

Further reading