Creating a function to log all the hierarchies in the array order by the level

Question

I am trying to create a function which logs all of the hierarchies in the array order by the level.

tried a lot of things but couldn't really figure out.

would like if you can help me out.

const arr = [
  { id: 1, parent_id: 8, level: 2, name: "person1" },
  { id: 2, parent_id: 1, level: 3, name: "person2" },
  { id: 8, parent_id: 0, level: 1, name: "person3" }
];

const func = (arr, level) => {

}

so the hierarchy by giving level 3 will be person2 => person1(since parent_id is 1) => person3(since parent_id is 8)

Thanks for helping !

user_5625547 · Answer

One way is to change the function so you can call it recursively, then we can call 'ourself' until there are no parents found:

const arr = [
  { id: 1, parent_id: 8, level: 2, name: "person1" },
  { id: 2, parent_id: 1, level: 3, name: "person2" },
  { id: 8, parent_id: 0, level: 1, name: "person3" }
];

const getMatch = (arr, level, isParent = false) => {
  const key = (isParent) ? 'id' : 'level';
  const match = arr.filter(a => a[key] === level)[0];
  if (!match) { return false; }
  
  const parent = getMatch(arr, match.parent_id, true);
  return (parent) ? { ...match, parent } : match; 
}

const res = getMatch(arr, 3);
console.log(res);

{
  "id": 2,
  "parent_id": 1,
  "level": 3,
  "name": "person2",
  "parent": {
    "id": 1,
    "parent_id": 8,
    "level": 2,
    "name": "person1",
    "parent": {
      "id": 8,
      "parent_id": 0,
      "level": 1,
      "name": "person3"
    }
  }
}

user_17487348 · Answer

Here is another iterative solution to your problem that will also work for multiple employees on the same level.

This solution uses Maps to speedup the lookup time to O(1) instead of the array lookups which have a worst case runtime of O(n).

One map maps a person ID to a person's details and another one maps levels to person IDs. These maps need to be filled once in the beginning and can then later be used to speedup the creation of the trees.

Pre-processing

Here the pre-processing required to fill the Maps:

/**
 * @typedef TPerson
 * @property {number} id
 * @property {number} parent_id
 * @property {number} level
 * @property {string} name
 */

const arr = [
  { id: 1, parent_id: 8, level: 2, name: "person1" },
  { id: 4, parent_id: 1, level: 3, name: "person4" },
  { id: 2, parent_id: 1, level: 3, name: "person2" },
  { id: 8, parent_id: 0, level: 1, name: "person3" },
];

// pre-processing to have quick lookups in Maps instead of filtering arrays
const persons = new Map();
const levels = new Map();
arr.forEach((person) => {
  if (levels.has(person.level)) levels.get(person.level).push(person.id);
  else levels.set(person.level, [person.id]);
  persons.set(person.id, person);
});

/**
 * Print map for demo purposes (as console.log(map) does not work in SO snippets)
 * @param {Map
    console.log(`${key} => ${JSON.stringify(value)}`)
  );
}

console.log("Map of person ID to person details:");
printMap(persons);
console.log("Map of level to person IDs of persons on that level:");
printMap(levels);

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

Possible results

For the actual algorithm there are two ways to look at it and by your description either one of them could be what you actually want.

Get hierarchy for a given person

This gets the hierarchy for a specific person using his/ her ID. See function hierarchyForPerson() or hierarchyForPersonNested().

Get hierarchy for a given level

The hierarchy for a given level. In this case we could have multiple hierarchies take for instance the following hierarchy

In this case 4, 5 and 6 would be on the same level but have different hierarchies. In order to account for that the functions hierarchyForAllPersonsOnLevel() or hierarchyForAllPersonsOnLevelNested() return an object of hierarchies containing one hierarchy for each person on the given level.

Organize result

There also are two different ways to organize the result

Linear

Hierarchy is returned as an array where a person at index i in the array is the child of a person with index j in the array for all 0 <= i < j <= array.length. Take for instance this hierarchy:

      1
     / 
    2

The result for person 2 would here be [2, 1], meaning 2 is a child of 1. All functions without Nested at the end of their name will create the linear result.

Nested

The hierarchy is returned as an nested object which have a parent property which contains the parent. If there is no parent, there is no parent property (this could be changed as well). If we take the same hierarchy as above the result would be:

{
  id: 2,
  parent: {
    id: 1,
  }
}

All function with Nested at the end of their name will create the nested result.

Implementation

Here the implementation of the actual algorithm with pre-processing (but without unnecessary output).

In order to show that the implementation works for multiple persons on the same level as described I have added one more person ({ id: 4, parent_id: 1, level: 3, name: "person4" },) to your sample which is an additional person on level 3. The hierarchy therefore looks like this now:

/**
 * @typedef TPerson
 * @property {number} id
 * @property {number} parent_id
 * @property {number} level
 * @property {string} name
 */

const arr = [
  { id: 1, parent_id: 8, level: 2, name: "person1" },
  { id: 4, parent_id: 1, level: 3, name: "person4" },
  { id: 2, parent_id: 1, level: 3, name: "person2" },
  { id: 8, parent_id: 0, level: 1, name: "person3" },
];

// pre-processing to have quick lookups in Maps instead of filtering arrays
const persons = new Map();
const levels = new Map();
arr.forEach((person) => {
  if (levels.has(person.level)) levels.get(person.level).push(person.id);
  else levels.set(person.level, [person.id]);
  persons.set(person.id, person);
});

/**
 * Prints hierarchy for all persons on a level in a linear (non-nested way).
 * @param {Map} persons Map of person IDs to person details
 * @param {Map} levels Map of levels to person IDs on that level
 * @param {number} level level that is supposed to be printed
 * @returns one hierarchy for each person on a specified level
 */
function hierarchyForAllPersonsOnLevel(persons, levels, level) {
  if (!levels.has(level))
    throw new Error(`there is no person on level ${level}`);
  const allOnLevel = levels.get(level);
  return allOnLevel.reduce((allHierarchies, personId) => {
    allHierarchies[personId] = hierarchyForPerson(persons, personId);
    return allHierarchies;
  }, {});
}

/**
 * Prints hierarchy for all persons on a level in a nested way.
 * @param {Map} persons Map of person IDs to person details
 * @param {Map} levels Map of levels to person IDs on that level
 * @param {number} level level that is supposed to be printed
 * @returns one hierarchy for each person on a specified level
 */
 function hierarchyForAllPersonsOnLevelNested(persons, levels, level) {
  if (!levels.has(level))
    throw new Error(`there is no person on level ${level}`);
  const allOnLevel = levels.get(level);
  return allOnLevel.reduce((allHierarchies, personId) => {
    // only difference to non-nested structure is the call to hierarchyForPersonNested() instead of hierarchyForPerson()
    allHierarchies[personId] = hierarchyForPersonNested(persons, personId);
    return allHierarchies;
  }, {});
}

/**
 * Creates hierarchy for a given person.
 * @param {Map} persons Map of person IDs to person details
 * @param {number} id person ID
 * @returns an array where person a[i] is supervised by person a[j] for all i < j e.g. result [{id: 1}, {id: 2}] means 1 is supervised by 2
 */
function hierarchyForPerson(persons, id) {
  let curId = id;
  const hierarchy = [];
  while (persons.has(curId)) {
    const person = persons.get(curId);
    hierarchy.push(person);
    curId = person.parent_id;
  }
  return hierarchy;
}

/**
 * Creates hierarchy for a given person.
 * @param {Map} persons Map of person IDs to person details
 * @param {number} id person ID
 * @returns an array where person a[i] is supervised by person a[j] for all i < j e.g. result [{id: 1}, {id: 2}] means 1 is supervised by 2
 */
function hierarchyForPersonNested(persons, id) {
  let curId = id;
  let curHierarchy = {};
  let hierarchy = {};
  let isRoot = true;
  while (persons.has(curId)) {
    const person = persons.get(curId);
    if (isRoot) {
      curHierarchy = {...person};
      // let hierarchy always point to top most object
      hierarchy = curHierarchy;
      isRoot = false;
    } else {
      curHierarchy.parent = {...person};
      curHierarchy = curHierarchy.parent;
    }
    curId = person.parent_id;
  }
  return hierarchy;
}

console.log(`
+-----------------------------------
| Hierarchy for person with ID 2
+-----------------------------------`);
console.log("> Linear")
console.log(hierarchyForPerson(persons, 2));
console.log("> Nested")
console.dir(hierarchyForPersonNested(persons, 2), { depth: null });
console.log(`
+-----------------------------------
| Hierarchy for all persons on level 3
+-----------------------------------`);
console.log("> Linear");
console.log(JSON.stringify(hierarchyForAllPersonsOnLevel(persons, levels, 3), null, 2));
console.log("> Nested");
console.log(JSON.stringify(hierarchyForAllPersonsOnLevelNested(persons, levels, 3), null, 2));

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