I have a tree structure that is made out of the data below. I need a search algorithm to find the top leader when I put in anyone’s _id
value, regardless of leader or child.
For example, if the input is "615e8215c3055d1addc216b0"
(the id of Rahman) or "61164b4bc08f86505e7dcdd8"
(the id of Aaron Aziz) it should return the id of “Aaron Aziz” as he is the leader.
The data structure has essentially a 2 level structure where each top-level entry has references to its immediate children. Notice that a child may appear again as leader (at the top level) so to specify deeper connections:
"families": [ { "datecreated": "2021-10-06T07:39:28.988Z", "_id": "615d52cb7cc6d32978afa694", "leader": { "_id": "61164b4bc08f86505e7dcdd8", "name": "Aaron Aziz" }, "children": [ { "datejoined": "2021-10-06T07:39:28.988Z", "_id": "615d52cb7cc6d32978afa695", "child": { "_id": "615c15c66dd91a2d4385ac84", "name": "Amirul Adha" } }, { "datejoined": "2021-10-06T08:04:52.122Z", "_id": "615d58cf0f045f320cb28706", "child": { "_id": "615d58b40f045f320cb28701", "name": "Samirul Ali" } } ] }, { "datecreated": "2021-10-07T05:12:22.671Z", "_id": "615e8475c3055d1addc216b5", "leader": { "_id": "615c15c66dd91a2d4385ac84", "name": "Amirul Adha" }, "children": [ { "datejoined": "2021-10-07T05:12:22.671Z", "_id": "615e8475c3055d1addc216b6", "child": { "_id": "615e8215c3055d1addc216b0", "name": "Rahman" } } ] }, { "datecreated": "2021-10-07T08:52:47.840Z", "_id": "615eb630e0cc0d22281bb282", "leader": { "_id": "615e8215c3055d1addc216b0", "name": "Rahman" }, "children": [ { "datejoined": "2021-10-07T08:52:47.840Z", "_id": "615eb630e0cc0d22281bb283", "child": { "_id": "615eb60de0cc0d22281bb27d", "name": "Aizi" } } ] } ]
I’ve created a recursive function. But when I input a child without children, it returns the sibling instead of the parent.
const findLeader = (childId) => { let leader; for (const family of familiesCopy) { const isChild = family.children.find((i) => i.child._id == childId); leader = family.leader; if (isChild) { findLeader(family.leader._id); } if (!isChild) { return leader; } } return leader; };
How can I make it work?
Advertisement
Answer
I would suggest a function to first transform the structure, so each person can be looked up by id in constant time, giving their leader reference, children references and other properties.
So here is a makeGraph
function to do just that, and then getTopLeader
function to search that graph for a given child:
function makeGraph(families) { // Collect children and key by their id let graph = Object.fromEntries(families.flatMap(({ leader: { _id }, children }) => children.map(({ child, ...relation }) => [child._id, { ...child, leader: _id, relation, children: [], }]) )); // Collect leaders and key by their id, possibly extending existing entry for (let { leader, children, ...creation } of families) { Object.assign(graph[leader._id] ??= {}, { ...leader, creation, children: children.map(({child}) => child._id) }); } return graph; } function getTopLeader(graph, id) { if (!graph[id]) return; // Not found while (graph[id].leader) id = graph[id].leader; return id; } // Example run on question's data let obj = {"families": [{"datecreated": "2021-10-06T07:39:28.988Z","_id": "615d52cb7cc6d32978afa694","leader": {"_id": "61164b4bc08f86505e7dcdd8","name": "Aaron Aziz"},"children": [{"datejoined": "2021-10-06T07:39:28.988Z","_id": "615d52cb7cc6d32978afa695","child": {"_id": "615c15c66dd91a2d4385ac84","name": "Amirul Adha"}},{"datejoined": "2021-10-06T08:04:52.122Z","_id": "615d58cf0f045f320cb28706","child": {"_id": "615d58b40f045f320cb28701","name": "Samirul Ali"}}]},{"datecreated": "2021-10-07T05:12:22.671Z","_id": "615e8475c3055d1addc216b5","leader": {"_id": "615c15c66dd91a2d4385ac84","name": "Amirul Adha"},"children": [{"datejoined": "2021-10-07T05:12:22.671Z","_id": "615e8475c3055d1addc216b6","child": {"_id": "615e8215c3055d1addc216b0","name": "Rahman"}}]},{"datecreated": "2021-10-07T08:52:47.840Z","_id": "615eb630e0cc0d22281bb282","leader": {"_id": "615e8215c3055d1addc216b0","name": "Rahman"},"children": [{"datejoined": "2021-10-07T08:52:47.840Z","_id": "615eb630e0cc0d22281bb283","child": {"_id": "615eb60de0cc0d22281bb27d","name": "Aizi"}}]}]}; let graph = makeGraph(obj.families); let childid = "615e8215c3055d1addc216b0"; // Rahman let leaderid = getTopLeader(graph, childid); // 61164b4bc08f86505e7dcdd8 = Aaron Aziz console.log(`Leader of ${childid} is ${leaderid}`);
The graph
variable will be useful for other lookup tasks as well.