javascriptarraysrecursionmultidimensional-arraydepth

How can I add the correct depth value to a nested json object when children have multiple parents

I'm facing an issue when trying to add a depth value to each object to a nested array.

The specific issue I'm facing is that when an object has multiple siblings the depth is applied to the first but not the others, but I need each object to have a depth value.

var data = [
  { "title": "meta", "parentids": [] },
  { "title": "instagram", "parentids": ["meta"] },
  { "title": "facebook", "parentids": ["meta"] },
  { "title": "whatsapp", "parentids": ["meta"] },
  { "title": "zuckerberg", "parentids": ["instagram", "facebook"] },
]

// Assign a 'children' property to each object.
data.forEach(o => o.children = [])

// For each object assign a key/object pair
let map = data.reduce((a, o) => (a[o.title] = o, a), {})

// For each 'parentids' in each object in data push this object
data.forEach(o => o.parentids.forEach(pid => map[pid] && map[pid].children.push(o)))

let copyOfData = [...data];

let assignDepth = (arr, depth = 0, index = 0) => {
   if(index < arr.length){
      arr[index].depth = depth;
      if(arr[index].children.length){
         return assignDepth(arr[index].children, depth+1, 0);
      };
      return assignDepth(arr, depth, index+1);
   };
   return;
};

if (copyOfData.length) {
    assignDepth(copyOfData)
    console.log(copyOfData)
}

Solution

  • Rule of thumb with recursion: use it for depth (traversing deeper into trees), not breadth (iterating arrays). Use loops when iterating arrays, even if they're a "level" of a tree.

    In this case, your recursive function is overloaded to count along arrays as well as explore deeply. But using a loop for iterating children arrays saves a lot of work--you can drop the index parameter from the recursive call signature. Just use recursion where it's best: exploring deeper into the tree.

    const data = [
  {title: "meta", parentids: []},
  {title: "instagram", parentids: ["meta"]},
  {title: "facebook", parentids: ["meta"]},
  {title: "whatsapp", parentids: ["meta"]},
  {title: "zuckerberg", parentids: ["instagram", "facebook"]},
];

const titleLookup = Object.fromEntries(
  data.map(e => {
    e.children = [];
    return [e.title, e];
  })
);

for (const o of data) {
  for (const pid of o.parentids) {
    titleLookup[pid].children.push(o);
  }
}

const assignDepth = (arr, depth = 0) => {
  for (const e of arr) {
    e.depth ??= depth;
    assignDepth(e.children, depth + 1);
  }
};

assignDepth(data);
console.log(data);

    You could also assign node depth by traversing up the tree from each node to the root. If you hit a node that already has a depth, stop and use that as the baseline.

    Additional tips: