Convert a string tree to array

Question

I've got objects with an id as a string. Each object can be the child of another object. Relations can be guessed from IDs. For exemple:

[
  { id: '1:2:6', ids: ['1', '2', '6'] },
  { id: '1:4', ids: ['1', '4'] },
  { id: '1', ids: ['1'] },
  { id: '1:2', ids: ['1', '2'] },
]

In this exemple, root object is id: 1, which has 2 childrens id: 1:2 and id: 1:4. Finaly, id: 1:2 has a children id: 1:2:6.

I would like to convert this array to another array where childrens are embeded into parents, so the previous array would result in:

[
  {
    id: '1',
    children: [
      {
        id: '1:2',
        children: [
          { id: '1:2:6', children: [] }
        ],
      },
      {
        id: '1:4',
        children: [],
      }
    ],
  }
]

I can use ES6. I tried for hours to find a solution using all sort of loops but I can't figure this out. Any help would be appreciated!

Answer 1

You could iterate the objects and reduce ids by looking for an object at the actual level. If not found create a new object. Then return the children.

var data = [{ id: '1:2:6', ids: ['1', '2', '6'] }, { id: '1:4', ids: ['1', '4'] }, { id: '1', ids: ['1'] }, { id: '1:2', ids: ['1', '2'] }],
    tree = data.reduce((r, { ids }) => {
        ids.reduce((t, _, i, a) => {
            var id = a.slice(0, i + 1).join(':'),
                temp = t.find(o => o.id === id);
            
            if (!temp) t.push(temp = { id, children: [] });
            return temp.children;
        }, r);
        return r;
    }, []);

console.log(tree);

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 2

I think the iterative approach is more readable so maybe provided solution will help you understand how it is done (though it is lightly inspired by Nina's answer)

So what we do is iterate over all objects in the list. Initially, for each object, we set the current nodeList as the final tree. And we iterate over the length of ids.

First, we create the id form the list of ids by dividing the ids array into incrementally larger chunks with slice (['1'], ['1','2'], ['1', '2', '6') and concatenate to a string with :. So we get 1, 1:2, 1:2:6 ids for the first item.

Next, we find a node in currentNodelist by previously constructed id. If we cannot find the node that means we have not added it yet so we need to create and add it (If we find it then we don't need to do add it).

In the next step, we need to go deeper into the tree so we assign the currently created(or the one that we found) node's children as currentNodelist. With this, we traverse the tree deeper by provided ids.

let objs = [
  { id: '1:2:6', ids: ['1', '2', '6'] },
  { id: '1:4', ids: ['1', '4'] },
  { id: '1', ids: ['1'] },
  { id: '1:2', ids: ['1', '2'] },
];

let tree = [];
for (let i = 0; i < objs.length; i++) {
  let obj = objs[i];

  let currentNodeList = tree;
  for (let j = 0; j < obj.ids.length; j++) {
    let id = obj.ids.slice(0, j + 1).join(':');
    let currentNode = currentNodeList.find((node) => node.id === id);

    if (!currentNode) {
      currentNode = {id, children: []};
      currentNodeList.push(currentNode);
    } 

    currentNodeList = currentNode.children;
  }
}

console.log(tree);

I created a simple gif that shows what is happening in the first 2 iterations. The arrow is pointing to currentListNode.