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?

CodePudding user response：

Since you always want the first entry, you can use something like families[0] to access it. You won't need a search algorithm:

x = {your json data}
x["families"][0]["leader"]["name"]

Output:

'Aaron Aziz'

CodePudding user response：

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.