How to recursively build the path of sub-arrays inside an array with unknown depth

Question

I have an array structured like the following:

var persons= [{name: 'John',
               id: 1,
               children :[{name :'John Jr',
                           id: 11,
                           children :[{name: 'John Jr Jr'
                                      id: 111}]
                          },
                          {name :'Jane'
                           id: 12}]
             },
             {name:'Peter',
              id :2
             },
             ...]

It is basically an array of objects, the objects are persons, each person may have any number of descendants which are by them selves arrays of person objects. The number of descendants of each person is unknown.

What I am trying to achieve is to have a map structured this way:

var personsMap =[1 : 'John',
            11: 'John > John Jr',
            111 : 'John > John Jr > John Jr Jr',
            12: 'John > Jane',
            ...
           ]

It is a map of each possible combination of each path, so by querying the map by the person's id, it should return the string of it's parent > grand-parent >...

I'am trying to build this map recursively so what I have tried so far:

var personsMap = {};

function buildParentsMap (persons){
   $.each (persons, function(ndx, person){
      if(person.children && person.children.length > 0){
          buildParentsMap(person.children);
      }
      personsMap[person.id] = person.name; 
   });
   console.log(personsMap);
}

But this outputs the following :

[1 : 'John',
11: 'John Jr',
111 'John Jr Jr',
12: 'Jane',
...]

It is all the names but without being concatenated the way I explained above. How can I achieve this? Thanks

The numbering system is just an example to facilitate the understanding of the question. In my real situation ids are generated in a different way. — achref, Nov 23 '17 at 19:22
Possible duplicate of [How do you check if a variable is an array in JavaScript?](https://stackoverflow.com/questions/767486/how-do-you-check-if-a-variable-is-an-array-in-javascript) — , Nov 23 '17 at 19:39
Have you at least read fully the question before down vote? I see absolutely nothing in common with the duplicate — achref, Nov 23 '17 at 19:47

trincot · Accepted Answer · 2017-11-23T19:38:27.587

You could use this version of the function (ES6 code):

function buildParentsMap(persons, path = []) {
    return (persons || []).reduce( (acc, person) =>
            acc.concat({ [person.id]: path.concat(person.name).join(' > ') },
                       buildParentsMap(person.children, path.concat(person.name)))
        , []);
}
// Sample data
const persons=[{name: 'John',id: 1,children : [{name :'John Jr',id: 11,children :[{name: 'John Jr Jr',id: 111}]}, {name :'Jane',id: 12}]}, {name:'Peter', id :2 }];

const result = buildParentsMap(persons);
console.log(result);

.as-console-wrapper { max-height: 100% !important; top: 0; }

That is exactly what I need, thanks! (+1 for the clarity) – achref Nov 23 '17 at 19:36 — achref, Nov 23 '17 at 19:36

score 1 · Answer 2 · answered Nov 23 '17 at 21:24

The issue with the original buildParentsMap function is that, although it is successfully making recursive calls to add each person into the map, it doesn't build in any way to keep track of each child's ancestors. When buildParentsMap has been called on John Jr Jr, all it knows is info about the particular array that has been passed into it, which looks like this: [{name: 'John Jr Jr', id: 111}].

One way to solve this would be to add a second parameter to the buildParentsMap function to keep track of which ancestors, if any, need to be tacked onto whomever is currently being added to the map. For example:

var personsMap = {};

// Accept an optional "ancestors" argument in each function call
// so we know what prefix to append onto each child
function buildParentsMap (persons, ancestors){
    // If no ancestors, nothing needs to be appended
    // so set to empty string
    if( !ancestors ) ancestors = "";

    // Loop through all people in the array
    for(let idx in persons){

        let person = persons[idx];

        if(person.children && person.children.length > 0){
            // If this person has children, make a recursive call on the
            // children. Include the current person as an ancestor
            let prefix = ancestors + person.name + " > ";
            buildParentsMap(person.children, prefix);
        }

        personsMap[person.id] = ancestors + person.name;
    }
}

If we test it using your example array:

var personsExample = [
    { name: 'John',
      id: 1,
        children: [
            {
                name: 'John Jr',
                id: 11,
                children: [
                    {
                        name: 'John Jr Jr',
                        id: 111
                    }
                ]
            },
            {
                name: 'Jane',
                id: 12
            }
        ]
    },
    {
        name:'Peter',
        id: 2
    }
];

buildParentsMap(personsExample);
console.log(personsMap);

The output now appears like so:

{ 1: 'John',
  2: 'Peter',
  11: 'John > John Jr',
  12: 'John > Jane',
  111: 'John > John Jr > John Jr Jr' }

Thanks for your help, the first answer already solved my problem. +1 For the explanation, that made things clearer in my mind! — achref, Nov 23 '17 at 22:35

How to recursively build the path of sub-arrays inside an array with unknown depth

2 Answers2