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
}

CodePudding user response：

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)

CodePudding user response：

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: []},
]
*/