Flat array to tree Javascript

Question

Looking for a javascript or typescript solution to turn this array of sql data into a tree structure:

Some other solutions I've tried set the id as a property in the expected array but not the key of the object like in the expected solution.

const sqlData = [
  { id: 1, label: 'root', parentId: 0 },
  { id: 2, label: 'ant', parentId: 1 },
  { id: 3, label: 'cat', parentId: 1 },
  { id: 4, label: 'bear', parentId: 3 },
  { id: 5, label: 'dog', parentId: 3 },
  { id: 6, label: 'elephant', parentId: 5 },
  { id: 7, label: 'frog', parentId: 1 },
];

const expected = [
  {
    1: {
      label: 'root',
      children: [
        {
          2: {
            label: 'ant',
            children: [],
          },
        },
        {
          3: {
            label: 'cat',
            children: [
              {
                4: {
                  label: 'cat',
                  children: [],
                },
              },
              {
                5: {
                  label: 'dog',
                  children: [
                    {
                      6: {
                        label: 'elephant',
                        children: [],
                      },
                    },
                  ],
                },
              },
            ],
          },
        },
        {
          7: {
            label: 'frog',
            children: [],
          },
        },
      ],
    },
  },
];

Answer 1

This can be done with O(n) time complexity by leveraging object references. By creating a children array on each element and then adding the correct child to its parent's children array, you can accomplish building the whole tree.

const sqlData=[{id:1,label:"root",parentId:0},{id:2,label:"ant",parentId:1},{id:3,label:"cat",parentId:1},{id:4,label:"bear",parentId:3},{id:5,label:"dog",parentId:3},{id:6,label:"elephant",parentId:5},{id:7,label:"frog",parentId:1}];

const parentMap = {};
const root = [];

// Map parent positions
sqlData.forEach((el, i) => {
  parentMap[el.id] = i;
  el.children = [];
});

sqlData.forEach(({ id, parentId, label, children }) => {
  const insert = { [id]: { label, children } };
  if (parentId === 0) {
    root.push(insert);
    return;
  }
  sqlData[parentMap[parentId]].children.push(insert);
});

console.log(root);