CODEWITHSUNDEEP
javascript
nonion
nonion

Reputation: 832

Finding closest ancestor

I got a problem that I'm trying to figure out, was hoping someone can help. The input is something like this:

{
    "John": ["Sam", "Megan"],
    "Sam": ["Donna", "Josh", "Flora"],
    "Megan": ["Stephanie", "Nathan"]
}

Where Sam and Megan are John's children, etc. I'm required to find the closest ancestor of 2 names. For example, Sam and Josh will return Sam, Donna and Josh will return Sam, etc. I have completed that part, however the problem is if they start to move the structure around, so instead of above, they change it to:

{
    "Sam": ["Donna", "Josh", "Flora"],
    "Megan": ["Stephanie", "Nathan"],
    "John": ["Sam", "Megan"]
}

then my code has trouble with it. Can someone give me some sort of hints on this? My JavaScript knowledge is very basic so if someone can help it'll be great.

Upvotes: 1

Views: 160

Answers (2)

Chris B
Chris B

Reputation: 733

My answer is based off of Lowest Common Ancestor algorithms which can be easily researched. It assumes that you know the name of the person at the root of the entire tree. It basically recursively searches the tree looking for the lowest node that contains both elements. Here is a JSFiddle containing a few names. Hope this helps.

function findAncestor(root, p1, p2) {
   if(!root)
      return "";

   if(root == p1 || root == p2)
      return root;
   else
   {
      var count = 0;
      var lastfound = -1;
      if(fam[root]) //make sure root exists in fam
      {
          for(var i = 0; i < fam[root].length; i++)
          {
              var res = findAncestor(fam[root][i], p1, p2); //recursively search trees
              if(res)
              {
                  count++;
                  lastfound = i;
              }
          }
      }

      if(count >= 2) //found in different subtrees so this is the ancestor
         return root;
      else if(count == 1)
          return fam[root][lastfound];
      else
          return "";
   }
}

Upvotes: 0

Travis J
Travis J

Reputation: 82287

Looking at lineage and family trees is literally examining a tree structure. As such, there are some similarities that can be taken advantage of. In a tree form, it would be depth. In this lineage model, it will be a generation number. Note that you were already doing this logically (based on index). Now you just need to make it concrete.

I am not sure what works best for how you are composing these. But when you know the order, that is when you need to either add that into the array or wrap this in an object.

Array version

{
 "Sam": [2,"Donna", "Josh", "Flora"],
 "Megan": [2,"Stephanie", "Nathan"],
 "John": [1,"Sam", "Megan"]
}

Object version

{
 "Sam": {"generation":2,"children":["Donna", "Josh", "Flora"]},
 "Megan": {"generation":2,"children":["Stephanie", "Nathan"]},
 "John": {"generation:1","children":["Sam", "Megan"]}
}

Or an even more preferable version would be to also assign some sort of unique identifier to the family line so that you can also distinguish between them.

{
 "Sam": {
  "family":"f31460e9",
  "generation":2,
  "children":["Donna", "Josh", "Flora"]
 },
 "Megan": {
  "family":"f31460e9",
  "generation":2,
  "children":["Stephanie", "Nathan"]},
 "John": {
  "family":"f31460e9",
  "generation:1",
  "children":["Sam", "Megan"]
 }
}

Upvotes: 1

Related Questions