Question 244304 in Javascript Question posted in
A very good W3school tutorial can be found here.

Javascript – 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)
}
Tags:

2

Answers


  1. 0

    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:

    • Use const rather than let and var. Only use let on rare occasions when you really need to reassign something, like a loop counter.
    • let copyOfData = [...data]; is a bit misleading, because it’s barely a copy–the only thing that’s copied here is the outermost array. All of the objects inside of it are the same. Maybe call this shallowCopy or something. If you really want to copy the whole original structure, you’ll need recursion, or a function that recurses internally, like JSON.parse(JSON.stringify(data)).
    Login or Signup to reply.
  2. 0

    This is @ggorlen’s idea to trace lineage spelled out. I think this is simpler to read, and it doesn’t create an intermediate structure (at the expense of speed for a very large data set).

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

// Count the (max) steps to from a node with given title to a root node.
// A root node has no (valid) parentids.
const depthOf = title => {
  const node = data.find(node => node.title === title);
  if (!node || !node.parentids.length) return 0;
  return 1 + Math.max(...node.parentids.map(depthOf));
}

// Annotate each data object with its depth.
const withDepth = data.map(obj => {
  return { ...obj, depth: depthOf(obj.title) }
})

console.log(withDepth)

    Probably fine for tree depths in the low hundreds and data arrays in the high hundreds or low thousands. You’d need to test at that scale to confirm.

    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search