Как построить иерархическую структуру из плоского массива в JavaScript

Оффтоп javascript
1

Привет, ребята! У меня есть массив с объектами, и я хочу превратить его в дерево. Каждый объект имеет уровень, который помогает определить его место в структуре.

Исходный массив:

const items = [
    {
        uid: 10,
        title: 'Категория А',
        depth: 1
    },
    {
        uid: 20,
        title: 'Категория Б',
        depth: 2
    },
    {
        uid: 30,
        title: 'Категория В',
        depth: 3
    },
    {
        uid: 40,
        title: 'Категория Г',
        depth: 4
    }
];

Ожидаемый результат:

const result = {
    uid: 10,
    title: 'Категория А',
    depth: 1,
    children: {
        uid: 20,
        title: 'Категория Б',
        depth: 2,
        children: {
            uid: 30,
            title: 'Категория В',
            depth: 3,
            children: {
                uid: 40,
                title: 'Категория Г',
                depth: 4,
                children: []
            }
        }
    }
};

Порядок элементов в массиве может быть различным, но дерево необходимо строить по уровню depth. Пустой массив children обозначает конечный узел. Как лучше всего это реализовать?

2

Стек тут проще рекурсии. Создаешь стек узлов, идешь по отсортированному массиву. Для каждого элемента ищешь подходящий уровень в стеке. Если depth больше предыдущего - добавляешь в children к последнему элементу стека. Если меньше - удаляешь лишние и ищешь нужный parent. Быстро работает и без головняка с вложенными вызовами.

3

Map здесь идеален. Создайте карту, где ключ - это depth, а значение - ссылка на узел для этого уровня. Пройдитесь по массиву: для каждого элемента проверьте, есть ли родитель с depth-1 в карте. Если есть, добавьте к его children. Если нет, это корневой узел. А дети точно должны быть объектом?