Árboles y árboles binarios

¿Qué es un árbol?

Un árbol es una estructura de datos jerárquica con nodos conectados por aristas. El nodo superior es la raíz y los nodos sin hijos son hojas. Los árboles binarios tienen como máximo 2 hijos por nodo.

Recorridos de árboles

// Inorder (Left, Root, Right) - Gives sorted order in BST
function inorder(root, result = []) {
  if (!root) return result;
  inorder(root.left, result);
  result.push(root.value);
  inorder(root.right, result);
  return result;
}

// Preorder (Root, Left, Right)
function preorder(root, result = []) {
  if (!root) return result;
  result.push(root.value);
  preorder(root.left, result);
  preorder(root.right, result);
  return result;
}

// Postorder (Left, Right, Root)
function postorder(root, result = []) {
  if (!root) return result;
  postorder(root.left, result);
  postorder(root.right, result);
  result.push(root.value);
  return result;
}

// Level Order (BFS)
function levelOrder(root) {
  if (!root) return [];
  const result = [], queue = [root];
  while (queue.length) {
    const level = [], size = queue.length;
    for (let i = 0; i < size; i++) {
      const node = queue.shift();
      level.push(node.value);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    result.push(level);
  }
  return result;
}