My MongoDB has some JSON data that looks like this:
[
{
"_id": {
"$oid": "1"
},
"name": "A Inc",
"children": [
{"$oid": "2"},{"$oid": "3"}],
"kind": "Organisation"
},
{
"_id": {
"$oid": "2"
},
"name": "ACS",
"children": [{"$oid": "4"}],
"kind": "Organisation"
},
{
"_id": {
"$oid": "3"
},
"name": "ABC Inc",
"children": [],
"kind": "Organisation"
},
{
"_id": {
"$oid": "5"
},
"name": "Disney",
"children": [some other ids],
"kind": "Channel"
},
...
]
I am trying to figure out how to create a forest or multiple trees without knowing the root of each tree. Ideally, I want to generate a data structure using a recursive method to link all the data together. However, I'm running into an issue where there are duplicated layers at times, as shown in the images below:
https://i.sstatic.net/afjJJ.png https://i.sstatic.net/pIlE4.png https://i.sstatic.net/AnlkJ.png
Some grandchildren are still within children, so I need an algorithm to handle this situation. If an id is in the leaf layer, it should not appear in upper layers, meaning each id should theoretically only appear once.
Here is my current implementation:
const data = require("./nodes.json");
function createTree(data, rootId) {
const root = data.find((item) => item._id.$oid === rootId);
if (!root) return null;
const children = root.children.map((child) => createTree(data, child.$oid));
return {
...root,
children,
};
}
function prettyPrint(node, level = 0) {
if (node.children) {
node.children.forEach((child) => {
console.log(
`${" ".repeat(level)} (${child.kind}) ${child.name} ${child._id.$oid}`
);
prettyPrint(child, level + 2);
});
}
}
const forest = data.map((item) => createTree(data, item._id.$oid));
prettyPrint(forest);
The desired structure would look like this, but it's uncertain if 1 and 2 are roots or if there might be another root like 99. The only way to know for sure may be to build the tree from the data and then find the root within the data structure.