Построение иерархического дерева из списка категорий

Условие

Необходимо реализовать функцию, принимающую массив объектов, каждый из которых имеет два свойства — title (название) и parent (родитель). Функция должна преобразовать такой плоский массив в вложенную структуру дерева, размещая элементы под их соответствующими родителями.

 const categories = {

    "title": "Приготовление напитков",
    "parent": "Техника для кухни"
};

    "title": "Техника для дома",
    "parent": "Бытовая техника"
};

    "title": "Веренные панели",
    "parent": "Встраиваемся техника"
};

    "title": "Бытовая техника",
    "parent": null
};

    "title": "Встраиваемся техника",
    "parent": "Бытовая техника"
};

    "title": "Духовые входы",
    "parent": "Встраиваемся техника"
};

    "title": "Продукты питания",
    "parent": null
};

    "title": "Электронаймики и термопоты",
    "parent": "Техника для кухни"
};

    "title": "Вытяжки",
    "parent": "Встраиваемся техника"
};

    "title": "Техника для кухни",
    "parent": "Бытовая техника"
}

Ответ

Сначала создайте узлы по уникальным title, затем привяжите каждый к parent. Исходный пример нужно оформить как корректный массив объектов.

function buildTree(categories) {
  const nodes = new Map();
  for (const item of categories) {
    if (nodes.has(item.title)) throw new Error('Повтор title');
    nodes.set(item.title, { ...item, children: [] });
  }
  const roots = [];
  for (const node of nodes.values()) {
    if (node.parent === null) roots.push(node);
    else {
      const parent = nodes.get(node.parent);
      if (!parent) throw new Error('Родитель не найден');
      parent.children.push(node);
    }
  }
  const visited = new Set(), stack = [...roots];
  while (stack.length) {
    const node = stack.pop();
    if (visited.has(node)) throw new Error('Некорректное дерево');
    visited.add(node);
    for (const child of node.children) stack.push(child);
  }
  if (visited.size !== nodes.size) throw new Error('Цикл в родителях');
  return roots;
}

Возвращается лес: корней может быть несколько. При одном parent на узел недостижимые из корней узлы означают цикл. Время и память O(n) при обычной Map.