Сбор всех значений узлов дерева

Условие

Требуется реализовать функцию collectValues, которая возвращает массив со значениями всех вершин переданного дерева.

const root = {
  value: 1,
  children: [
    {
      value: 2,
      children: [
        { value: 4 },
        { value: 5 },
      ],
    },
    {
      value: 3,
      children: [
        { value: 6 },
        { value: 7 },
      ],
    },
  ],
};

collectValues(root); // => [1, 2, 3, 4, 5, 6, 7]

Ответ

Пример требует обхода в ширину: сначала корень, потом его дети, затем следующий уровень. Используйте очередь и индекс чтения, чтобы не делать дорогой shift на каждом шаге.

function collectValues(root) {
  if (!root) return [];
  const queue = [root], values = [];
  for (let head = 0; head < queue.length; head++) {
    const node = queue[head];
    values.push(node.value);
    for (const child of node.children ?? []) queue.push(child);
  }
  return values;
}

Для данного дерева получится [1,2,3,4,5,6,7]; обычный DFS дал бы иной порядок. Предполагается именно дерево без циклов. Время O(n), память O(n) для очереди и результата.