Как найти имена всех белок в дереве

Условие

Дерево состоит из узлов {type, name, children}; children — массив, отсутствующий у листа. Нужно собрать имена type='squirrel' в порядке прямого обхода. Циклических ссылок нет.

Ответ

Обойдите узел, добавьте имя при совпадении типа и рекурсивно посетите детей слева направо. Время линейно по числу узлов.

Решение:

function squirrels(root) {
  const names = [];
  function visit(node) {
    if (node.type === 'squirrel') names.push(node.name);
    for (const child of node.children ?? []) visit(child);
  }
  if (root) visit(root);
  return names;
}

Для корня-белки Acorn с детьми-белками Sirsalty, Macadamia и Kernel получатся эти четыре имени. Ворон функция пропустит, но их детей всё равно проверит.