Create hierarchy from flat array with children IDs

Question

I have a flat array where each node has an ID and an array of the IDs of its children:

[
  {id: 1, children: [2, 3]}, 
  {id: 2, children: []}, 
  {id: 3, children: [4]}, 
  {id: 4, children: []}, 
  {id: 5, children: []},
]

How can I, preferably in Javascript, create a hierarchy with the actual objects as nested children instead of just their IDs?

[
  {id: 1, children: [
    {id: 2, children: []}, 
    {id: 3, children: [
      {id: 4, children: []}
     ]}
  ]},
  {id: 5, children: []},
]

I have tried the following but it only works the first layer:

function getHierarchyFromFlatArray(nodes) {
    const nodeById = new Map(nodes.map(el => [el.id, el]))
    for (const node of nodes) {
        node.children = node.children.map(id => { 
            let val = nodeById.get(id)
            let idx = nodes.findIndex(item => item.id=== id)
            nodes.splice(idx, 1)
            return val
        })
    }
    return nodes
}

take a look here https://stackoverflow.com/questions/18017869/build-tree-array-from-flat-array-in-javascript — Guy Nachshon, Apr 21 '22 at 07:38
@GuyNachshon In those examples, they have access to the parent key which I do not. I've found plenty of resources for that particular case, but not for when you only have children keys. — delicateSchedule, Apr 21 '22 at 07:46

score 3 · Accepted Answer · answered Apr 21 '22 at 07:46

Here's one way to solve the problem. First build a Map referencing the id values to the node value. Then process each of the nodes (replacing the list of children with a tree recursively, at the same time deleting those nodes from the Map) in the list if its id value is present in the Map.

const nodes = [
  {id: 1, children: [2, 3]}, 
  {id: 2, children: []}, 
  {id: 3, children: [4]}, 
  {id: 4, children: []}, 
  {id: 5, children: []},
]

const nodemap = new Map(nodes.map(n => [n.id, n]));

const tree = (node) => {
  nodemap.delete(node.id);
  return node.children.length ? {
    id : node.id, 
    children : node.children.map(c => tree(nodemap.get(c)))
  } 
  : node
}
  
result = []

nodes.forEach(node => {
  if (nodemap.has(node.id)) result.push(tree(node))
})

console.log(result)

relaxxpls · Answer 2 · 2022-04-21T08:00:06.023

Steps:

Create a mapping of each node to its parent (undefined for root nodes).
Clear the children array and begin attaching each node to the children array of its parent.
Finally return the nodes which have the parent key as undefined in our mapping.

const getHierarchyFromFlatArray = (nodes) => {
    const nodeById = {}
    const parent = {}

    nodes.forEach((node) => {
        nodeById[node.id] = node
        node.children.forEach((child) => {
            parent[child] = node.id
        })
        node.children = []
    })

    nodes.forEach((node) => {
        const parentId = parent[node.id]
        // ? If current node is the child of some other node
        if (parentId && nodeById[parentId]) {
            nodeById[parentId].children.push(node)
        }
    })

    return nodes.filter((node) => parent[node.id] === undefined)
}

const input = [
  {id: 1, children: [2, 3]}, 
  {id: 2, children: []}, 
  {id: 3, children: [4]}, 
  {id: 4, children: []}, 
  {id: 5, children: []},
]

const output = getHierarchyFromFlatArray(input)
console.log(output)

/*
output = [
  {id: 1, children: [
    {id: 2, children: []}, 
    {id: 3, children: [
      {id: 4, children: []}
     ]}
  ]},
  {id: 5, children: []},
]
*/

Create hierarchy from flat array with children IDs

2 Answers2