Reverse Array Travarsal using javascript

Question

I'm working with the objects where it requires to traverse from Children to Parents and here main issue is that one children can have multiple parents.

I have created tree with visjs as below.

I have array of Object as below.

{
    ChildId:63
    CostObjectHierarchyId:10064
    ParentId:1
},
{
    ChildId:64
    CostObjectHierarchyId:10066
    ParentId:1
},
{
    ChildId:65
    CostObjectHierarchyId:10068
    ParentId:1
},
{
    ChildId:66
    CostObjectHierarchyId:10069
    ParentId:1
},
{
    ChildId:67
    CostObjectHierarchyId:10071
    ParentId:1
},
{
    ChildId:68
    CostObjectHierarchyId:10074
    ParentId:1
},
{
    ChildId:59
    CostObjectHierarchyId:10057
    ParentId:58
},
{
    ChildId:60
    CostObjectHierarchyId:10060
    ParentId:59
},
{
    ChildId:61
    CostObjectHierarchyId:10061
    ParentId:60
},
{
    ChildId:62
    CostObjectHierarchyId:10062
    ParentId:61
},
{
    ChildId:58
    CostObjectHierarchyId:10063
    ParentId:63
},
{
    ChildId:58
    CostObjectHierarchyId:10065
    ParentId:64
},
{
    ChildId:58
    CostObjectHierarchyId:10067
    ParentId:65
},
{
    ChildId:68
    CostObjectHierarchyId:10072
    ParentId:66
},
{
    ChildId:59
    CostObjectHierarchyId:10075
    ParentId:67
},
{
    ChildId:59
    CostObjectHierarchyId:10076
    ParentId:68
}

Now my query is suppose I select Node L4 (61) then it should traverse reversely and I want to have all the nodes. Expected result is (60,59,58,68,63,64,65,66,67).

I'm trying to call loop reversely till parent Id '1' (Global) is found. but whenever there's multiple parents , I'm not able to get.

Example. Say I selected 60 then it has 59 as parent, but now 59 has 3 parents 58,68,67. Let any how I found this 3 then still for each I should be able to get their respective parents. so 58 has three parents 63,64,65. That's not able to get.

My Code is as below.

// Get Selected Node
var indEdge = _.findIndex($scope.COHData, { 'ChildId': $scope.objectId });
var itsParentId = 1;
var parentsArraySoFar = [];

_.each($scope.COHData, function (data) { // Till whole Array is traversed
    while (true) {
        if (indEdge > -1) {
            itsParentId = $scope.COHData[indEdge].ParentId; // Getting Parent Id of it.
            if (parseInt(itsParentId) === parseInt("1")) { // Will check if it's parent is 1 then stop
                parentsArraySoFar.push({ 'pid': itsParentId });
                break;
            }
            else {
                parentsArraySoFar.push({ 'pid': itsParentId });
                // Else search for next parent passing the resultant parent
                indEdge = _.findIndex($scope.COHData, { 'ChildId': itsParentId }); 
            }
        }
        else {
            break;
        }
    }
});

Thanks

code-jaff · Accepted Answer · 2016-12-30 04:37:38Z

Think in a bit different way

construct intermediary data structure which is a map of parents for each item
Traverse recursively with required child

Let me show you an example

var items = [{
  ChildId: 63,
  CostObjectHierarchyId: 10064,
  ParentId: 1
}, {
  ChildId: 64,
  CostObjectHierarchyId: 10066,
  ParentId: 1
}, {
  ChildId: 65,
  CostObjectHierarchyId: 10068,
  ParentId: 1
}, {
  ChildId: 66,
  CostObjectHierarchyId: 10069,
  ParentId: 1
}, {
  ChildId: 67,
  CostObjectHierarchyId: 10071,
  ParentId: 1
}, {
  ChildId: 68,
  CostObjectHierarchyId: 10074,
  ParentId: 1
}, {
  ChildId: 59,
  CostObjectHierarchyId: 10057,
  ParentId: 58
}, {
  ChildId: 60,
  CostObjectHierarchyId: 10060,
  ParentId: 59
}, {
  ChildId: 61,
  CostObjectHierarchyId: 10061,
  ParentId: 60
}, {
  ChildId: 62,
  CostObjectHierarchyId: 10062,
  ParentId: 61
}, {
  ChildId: 58,
  CostObjectHierarchyId: 10063,
  ParentId: 63
}, {
  ChildId: 58,
  CostObjectHierarchyId: 10065,
  ParentId: 64
}, {
  ChildId: 58,
  CostObjectHierarchyId: 10067,
  ParentId: 65
}, {
  ChildId: 68,
  CostObjectHierarchyId: 10072,
  ParentId: 66
}, {
  ChildId: 59,
  CostObjectHierarchyId: 10075,
  ParentId: 67
}, {
  ChildId: 59,
  CostObjectHierarchyId: 10076,
  ParentId: 68
}];

function construct(items) {
  var parentMap = {};
  items.forEach(function(item) {
    var mapItem = parentMap[item.ChildId];
    if (mapItem) {
      mapItem.push(item.ParentId);
    } else {
      parentMap[item.ChildId] = [item.ParentId];
    }
  });
  return parentMap;
}

var parents = [];
var map = construct(items);

function getParents(id) {
  map[id].forEach(function(innerId) {
    if (innerId === 1) {
      return;
    }
    parents = parents.concat(innerId);
    getParents(innerId);
  });
  return parents;
}

console.log(getParents(61));

Collectives™ on Stack Overflow

Reverse Array Travarsal using javascript

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related