Recursive data structure separate each branch

Question

I have a recursive data structure like the example below, the goal I hope it can be each branch, from null (parentTagId) extend to as long as final one.

I have no idea how to do it, any suggestion will be appreciated!!

origin data:

[ 
  { TagId: 2, ParentTagId: null, Name: 'women' },
  { TagId: 5, ParentTagId: 2, Name: 'bottom' },
  { TagId: 4, ParentTagId: 2, Name: 'top' },
  { TagId: 7, ParentTagId: 4, Name: 'shirt' },
  { TagId: 8, ParentTagId: 4, Name: 'tshirt' },
  { TagId: 12, ParentTagId: 7, Name: 'longsleeve' },
  { TagId: 16, ParentTagId: null, Name: 'men' }
]

Expected result:

women > bottom  
women > top > shirt > longsleeve   
women > tshirt  
men  

output data:

[
  {
    path: [ 
      { TagId: 2, ParentTagId: null, Name: 'women' },
      { TagId: 5, ParentTagId: 2, Name: 'bottom' }
    ]
  },
  {
    path: [
      { TagId: 2, ParentTagId: null, Name: 'women' },
      { TagId: 4, ParentTagId: 2, Name: 'top' },
      { TagId: 7, ParentTagId: 4, Name: 'shirt' },
      { TagId: 12, ParentTagId: 7, Name: 'longsleeve' }
    ]
  },
  {
    path: [
      { TagId: 2, ParentTagId: null, Name: 'women' },
      { TagId: 4, ParentTagId: 2, Name: 'top' },
      { TagId: 8, ParentTagId: 4, Name: 'tshirt' }
    ]
  },
  {
    path: [
      { TagId: 16, ParentTagId: null, Name: 'men' }
    ]
  }
]

Answer 1

Consider your input data as a tree. You want to generate the path to each leaf. A leaf is a tag with a TagId that is not referenced as ParentTagId by any other tag.

So the easiest solution would be:

1. Iterate over all tags and build a set (i.e. a list with unique entries) of all ParentTagId values. For your data, that is [2,4,7].
2. Find your leaves by iterating over all tags and picking those where the TagId is not in that set. For your data, that is [5,8,12,16].
3. Write a function getTagById to retrieve a tag by its id.
4. Write a recursive function to generate the path.
5. Iterate over all leaves and push the result of getPath([], leaf) into an array paths. After that, paths contains the path to each leaf as array of tags.
6. Build your output based on paths.

Code for step 1:

var parentTagIdSet = [];
for (var i = 0; i < originData.length; ++i) {
  var parentTagId = originData[i].ParentTagId;
  if (parentTagId != null && parentTagIdSet.indexOf(parentTagId) == -1) {
    parentTagIdSet.push(parentTagId);
  }
}

Code for step 2:

var leaves = [];
for (var i = 0; i < originData.length; ++i) {
  var tag = originData[i];
  if (parentTagIdSet.indexOf(tag.TagId) == -1) {
    leaves.push(tag);
  }
}

Code for step 3:

function getTagById(id) {
  for (var i = 0; i < originData.length; ++i) {
    var tag = originData[i];
    if (tag.TagId == id) {
      return tag;
    }
  }
  // If you finish the loop without returning, a ParentTagId is wrong.
  return null;
}

Code for step 4:

function getPath(path, currentTag) {
   if (currentTag == null) {
     // If you end up in here, some ParentTagId was wrong.
     path.reverse();
     return path;
   }
   path.push(currentTag);
   var parentId = currentTag.ParentTagId;
   if (parentId == null) {
     path.reverse();
     return path;
   } else {
     return getPath(path, getTagById(parentId));
   }
 }

Code for step 5:

var paths = [];
for (var i = 0; i < leaves.length; ++i) {
  paths.push(getPath([], leaves[i]));
}