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
}
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)Steps:
undefined for root nodes).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: []},
]
*/