Вложенное дерево — как достать все id?

Question

[Scott]

Есть такая структура данных:

const data = [
    {
        id: 0,
        children: [
            { id: '0_1' }, 
            { id: '0_2' }
        ]
    },
    {
        id: 1,
        children: [
            {
                id: '1_1',
                children: [
                    { id: '1_1_1' }, 
                    { id: '1_1_2' }
                ]
            }, 
            { id: '1_2' }
        ]
    }
]

Моя задача собрать все id, которые находятся внутри children, в том порядке в котором они идут в этом дереве.
Вложенность может быть любая, как и значение у id (строка или число).
В целом у меня это получилось, но мне не совсем нравится мой код, как его можно улучшить?

function getChildrenIds(arr) {
  return arr.reduce((acc, child) => {
    if (!child.children) {
      acc.push(child)
    }
    else if (!child.children.some(child => child.children)) {
      acc.push(child.children)
    } else {
      const deepChildren = getChildrenIds(child.children);
      return [...acc, ...deepChildren]
    }

    return acc.flat();
    // Пытался вернуть все id такой записью: 
    // return acc.flat(Infinity).map(({ id }) => id);
  }, [])
}

const ids = getChildrenIds(data, 'children').map(({ id }) => id)
console.log(ids) // ["0_1", "0_2", "1_1_1", "1_1_2", "1_2"]

К примеру, мне не нравится

• куча условий (но без них не представляю как это написать)
  
• не могу сразу вернуть массив всех id внутри функции (вместо этого отдельно вынужден использовать map)
  

Comments

[Kovalsky]

"не могу сразу вернуть массив всех id внутри функции" - ну так а что вам мешает класть в аккумулятор не весь объект, а только значение id? Чтобы на выходе получился нужный массив

Answer 1

[0xD34F]

Рекурсия есть:

const getFromTree = (tree, childrenKey, getter = n => n) =>
  Array.isArray(tree)
    ? tree.flatMap(n => [
        getter(n),
        ...getFromTree(n[childrenKey], childrenKey, getter),
      ])
    : [];

// или

function* flatTree(tree, childrenKey) {
  if (
    tree instanceof Object &&
    tree[Symbol.iterator] instanceof Function
  ) {
    for (const n of tree) {
      yield n;
      yield* getFromTree(n[childrenKey], childrenKey);
    }
  }
}

Рекурсии нет:

const getFromTree = function(tree, childrenKey, getter = n => n) {
  const result = [];

  for (const stack = this(tree); stack.length;) {
    const n = stack.pop();
    result.push(getter(n));
    stack.push(...this(n[childrenKey]));
  }

  return result;
}.bind(x => x instanceof Array ? [...x].reverse() : []);

// или

const flatTree = function*(tree, childrenKey) {
  const stack = [];

  for (let [ i, arr ] = this(tree); ++i < arr.length || stack.length;) {
    if (i === arr.length) {
      [ i, arr ] = stack.pop();
    } else {
      yield arr[i];
      stack.push([ i, arr ]);
      [ i, arr ] = this(arr[i][childrenKey]);
    }
  }
}.bind(x => [ -1, x?.constructor === Array ? x : [] ]);

Достаём id:

// т.к. id верхнего уровня получать не желаете, избавимся от него
const withoutTopLevel = data.flatMap(n => n.children);

// если использовать обычную функцию
const ids = getFromTree(withoutTopLevel, 'children', n => n.id);
// или, генератор
const ids = Array.from(flatTree(withoutTopLevel, 'children'), n => n.id);

Comments

[Scott]

обалдеть, большое спасибо!

Answer 2

[Антон Шаманов]

почитай про рекурсивный вызов функций

Comments

[Scott]

я как раз его и использовал

[Антон Шаманов]

Scott, сорян туплю, используй lodash там есть набор простых и полезных функций в том числе выборка по полю. еще есть неплохой сборник портов с php - https://javascript.ru/php

либо можно использовать es5+ (+ babel для совместимости):

function getByColumn(multiArray, column) {
  return multiArray.map(data => (typeof data[column] == "object" ? getByColumn(data[column], column) : data[column]) )
}