Интересная задачка JavaScript с построением дерева объектов

TREE.md

Tip

Написать функцию, которая преобразует этот плоский массив в вложенное дерево, null - это родитель

nature
   ├── animals
   │     ├── dogs
   │     └── cats
   └── plants

const categories = [
  { id: 'animals', parent: 'nature' },
  { id: 'nature', parent: null },
  { id: 'dogs', parent: 'animals' },
  { id: 'cats', parent: 'animals' },
  { id: 'plants', parent: 'nature' }
];

Important

Этот метод часто называют «сборкой дерева через ссылки» (Reference-based tree construction). Его главная фишка в том, что мы используем промежуточный объект map, чтобы мгновенно находить родителя по его ID.

function buildTree(items) {
  const rootItems = []; // Здесь будут лежать только корневые элементы
  const lookup = {};    // Вспомогательный объект-карта

  // 1. Сначала инициализируем карту (создаем объекты с полем children)
  for (const item of items) {
    lookup[item.id] = { ...item, children: [] };
  }

  // 2. Раскладываем детей по родителям
  for (const item of items) {
    const currentItem = lookup[item.id];
    const parentId = item.parent;

    if (parentId === null) {
      // Если родителя нет — это корень дерева
      rootItems.push(currentItem);
    } else {
      // Если родитель есть — кладем текущий объект в массив детей родителя
      // Благодаря ссылкам, объект обновится везде
      if (lookup[parentId]) {
        lookup[parentId].children.push(currentItem);
      }
    }
  }

  return rootItems;
}

const tree = buildTree(categories);
console.log(JSON.stringify(tree, null, 2));