Как из вложенных массивов выбрать нужные элементы без рекурсии?

Question

[AlexAll]

Есть массив объектов:

[
    {
        "id": 1,
        "name": "Бумага",
        "children" :[
            {
                "id": 2,
                "name": "Бумага офисная",
                "children" :[
                    {
                        "id": 3,
                        "name": "Бумага для принтера"
                    },
                    {
                        "id": 4,
                        "name": "Бумага для цветная"
                    }
                ]

            }
        ]
    },
    {
        "id": 5,
        "name": "Товары для офиса",
        "children" :[
            {
                "id": 6,
                "name": "Оборудование",
                "children" :[
                    {
                        "id": 7,
                        "name": "Для досок"
                    },
                    {
                        "id": 8,
                        "name": "Бэйджики"
                    }
                ]

            }
        ]
    },
    {
        "id": 9,
        "name": "Товары для школы",
        "children" :[
            {
                "id": 10,
                "name": "Подарки",
                "children" :[
                    {
                        "id": 11,
                        "name": "Конфеты"
                    },
                    {
                        "id": 12,
                        "name": "Игрушки"
                    }
                ]

            }
        ]
    }
]

Нужно выбрать элементы без children, т.е.

[
		{
                        "id": 3,
                        "name": "Бумага для принтера"
                    },
                    {
                        "id": 4,
                        "name": "Бумага для цветная"
                    },
                                {
                        "id": 7,
                        "name": "Для досок"
                    },
                    {
                        "id": 8,
                        "name": "Бэйджики"
                    },
		{
                        "id": 11,
                        "name": "Конфеты"
                    },
                    {
                        "id": 12,
                        "name": "Игрушки"
                    }
]

Можно это сделать без рекурсии?

Comments

[Вадим]

можно, но не нужно

[AlexAll]

Вадим, ну покажите, для самообразования)

[Вадим]

AlexAll, для самообразования могу статью предложить
https://habr.com/ru/post/533034/
Не уверен что она на 100% релеванта, так сам не читал, но, бегло пробежавшись - где то рядом.

[AlexAll]

Вадим, Там в статье как я понял, говорится что рекурсия зло, на большую глубину js ходить не может

[Вадим]

AlexAll, ну да, только "Большая" это штука относительная и для Вашего примера эта глубина с вероятностью близкой к 100% - недостижима. То есть для Вашего примера в это ограничение Вы не упрётесь. Очень маловероятно что у Вас будет цепочка из вложенных объектов на несколько тысяч звеньев

[AlexAll]

Вадим, ну это то да))
Ладно спасибо больше там ниже пример циклах написали)))

Answer 1

[0xD34F]

function getLeaves(tree) {
  const result = [];

  for (const stack = [...tree]; stack.length;) {
    const n = stack.pop();
    if (Array.isArray(n.children) && n.children.length) {
      stack.push(...n.children);
    } else {
      result.push(n);
    }
  }

  return result.reverse();
}

const leaves = getLeaves(tree);

или

const getFromTree = function*(tree, test) {
  const stack = [];

  for (let [ i, arr ] = this(tree); ++i < arr.length || stack.length;) {
    if (i === arr.length) {
      [ i, arr ] = stack.pop();
    } else {
      if (test(arr[i])) {
        yield arr[i];
      }

      stack.push([ i, arr ]);
      [ i, arr ] = this(arr[i].children);
    }
  }
}.bind(x => [ -1, x instanceof Array ? x : [] ]);

const leaves = [...getFromTree(tree, n => !n.children?.length)];

Comments

[AlexAll]

Это будет работать если вложенность у объектов будет разная?

[0xD34F]

AlexAll, разрешаю вам проверить это самостоятельно.

[AlexAll]

0xD34F, Спасибо большое