Извлечение значений листовых узлов из дерева

Условие

Сформулируйте функцию, которая получает на вход структуру дерева и возвращает массив со значениями всех конечных (leaf) узлов.

Ответ

Лист — узел без дочерних узлов. Обойдите дерево в глубину и добавляйте в ответ значение только таких узлов, сохраняя порядок детей.

function leafValues(root) {
  if (root == null) return [];
  const result = [], stack = [root];
  while (stack.length) {
    const node = stack.pop();
    const children = node.children ?? [];
    if (!children.length) result.push(node.value);
    else for (let i = children.length - 1; i >= 0; i--) stack.push(children[i]);
  }
  return result;
}

Выбран формат {value, children}; для другой структуры имена полей нужно адаптировать. Корень без детей сам является листом. Дети кладутся в стек справа налево, поэтому извлекаются слева направо. Предполагается дерево без циклов; время O(n), память обхода до O(n).