I am given an array, links:
const links = [
{parent: "flare", children: "analytics"} ,
{parent: "analytics", children: "cluster"} ,
{parent: "flare", children: "scale"} ,
{parent: "analytics", children: "graph"} ,
];
I want to make it into tree, like so:
const tree = {
"name": "flare",
"children": [
{
"name": "analytics",
"children": [
{
"name": "cluster",
},
{
"name": "graph",
}
]
}
]
};
Here is my attempt:
function buildTree(links) {
const map = { }
const findNodeInChildren = (name, obj) => {
if (obj[name]) {
return obj
} else if (!obj.children) {
return null
}
for (let i = 0; i < obj.children.length; i++) {
const found = findNodeInChildren(name, obj.children[i])
if (found) return found
}
return null
}
links.forEach(link => {
const foundNode = findNodeInChildren(link.parent, map)
if (!foundNode) {
const newNode = {
name: link.parent,
children: []
}
map[newNode.name] = newNode
} else {
foundNode[link.parent].children.push({
name: link.children,
children: []
})
}
})
return map
}
const links = [
{parent: "flare", children: "analytics"} ,
{parent: "analytics", children: "cluster"} ,
{parent: "flare", children: "scale"} ,
{parent: "analytics", children: "graph"} ,
];
const tree = buildTree(links)
const json = JSON.stringify(tree)
console.log(json)Here's the prettified JSON - it's not working as intended:
{
"flare": {
"name": "flare",
"children": [
{
"name": "scale",
"children": []
}
]
},
"analytics": {
"name": "analytics",
"children": [
{
"name": "graph",
"children": []
}
]
}
}
What is going wrong?
One of the issues in your code is when !foundNode is true, then you do not add the (first) child to its children array.
Secondly, the object your code returns is the map itself, obviously with at the top level a plain object with named keys, instead of an array of objects with "name" keys. The code should convert the map-structure (which is indeed nested) to the desired nested structure.
It is also strange that findNodeInChildren returns the whole map (i.e. obj) when the node is found. It would make more sense if obj[name] were returned, and the rest of the code were adapted to that.
You can also condense the code at bit more.
Here is how I would propose to do it:
const links = [
{parent: "flare", children: "analytics"} ,
{parent: "analytics", children: "cluster"} ,
{parent: "flare", children: "scale"} ,
{parent: "analytics", children: "graph"} ,
];
// Create a Map keyed by parent, so that for each parent there is a
// corresponding object, with (so far) empty children property.
// This uses the argument that can be passed to the Map constructor:
let map = new Map(links.map(({parent}) => [parent, { name: parent, children: [] }]));
// Iterate the input again, and look up each parent-related object,
// and insert there the child object, if found in the map, or otherwise
// create an object for it without a children property (it has none).
for (let {parent, children} of links) map.get(parent).children.push(map.get(children) ?? { name: children });
// Delete from the map all nodes that have a parent
for (let {children} of links) map.delete(children);
// What remains are the nodes at the top level (roots). Extract these
// objects from the map and store them as array
let result = [...map.values()];
console.log(result);This code returns an array, because the input structure does not guarantee there is only one root. It could represent a forest. If you are certain it is a tree (so with one root), then you can just pop the single element out of the array.