Can you transform a list to a tree where items in the list have children but no depth or parent?

Question

Data looks as follows:

• Each node has a unique id (
• Nodes have a children key which is either null or an array of ids.
• Nodes can have one parent
• Nodes do not have a parent or depth reference

Input:

const items = [
    {
      id: 1,
      name: 'Item 1',
      children: [ 2, 3 ]
    },
    {
      id: 2,
      name: 'Item 2',
      children: null
    },
    {
      id: 3,
      name: 'Item 3',
      children: null
    },
    {
      id: 4,
      name: 'Item 4',
      children: [ 5 ]
    },
    {
      id: 5,
      name: 'Item 5',
      children: [ 6 ]
    },
    {
      id: 6,
      name: 'Item 6',
      children: null
    },
  }
]

Expected Output:

const tree = [
  {
    id: 1,
    name: 'Item 1',
    children: [ 
      {
        id: 2,
        name: 'Item 2',
        children: null
      },
      {
        id: 3,
        name: 'Item 3',
        children: null
      }, 
    ]
  },
  {
    id: 4,
    name: 'Item 4',
    children: [ 
      {
        id: 5,
        name: 'Item 5',
        children: [
          {
            id: 6,
            name: 'Item 6',
            children: null
          }
        ]
      }
    ]
  }
]

If this is in fact possible, would love to 1) see how it is done and 2) see if there are any libraries that handle this use case.

Answer 1

The resulting structure is more a forest than a tree, as not all nodes are connected and you have multiple "roots".

You can first key the nodes by their id in a Map, and then iterate all children arrays to replace their contents by the corresponding items found in the Map. At the same time keep track of all the children, so that at the end you can identify which items are not children, and therefore belong in the result array:

const items = [{id: 1,name: 'Item 1',children: [ 2, 3 ]},{id: 2,name: 'Item 2',children: null},{id: 3,name: 'Item 3',children: null},{id: 4,name: 'Item 4',children: [ 5 ]},{id: 5,name: 'Item 5',children: [ 6 ]},{id: 6,name: 'Item 6',children: null},];

const map = new Map(items.map(item => [item.id, item]));
const children = new Set;
for (const item of items) {
    if (!item.children) continue;
    for (const id of item.children) children.add(id);
    item.children = item.children?.map(id => map.get(id));
}
const forest = items.filter(({id}) => !children.has(id));
console.log(forest);