CODEWITHSUNDEEP
javascriptarraysmultidimensional-array
Alex
Alex

Reputation: 67248

Build list of ancestors from nested array

The nested array looks like this:

var arr = [{
  id: 2,
  name: 'a',
  children: []
}, {
  id: 5,
  name: 'b',
  children: [{ 
    id: 14,
    name: 'b2'
  }]

}, {
  id: 15,
  name: 'd',
  children: []
}];

How can I make a list of ancestor elements, from any given element?

For example, if given element has id: 14 the list should return only the parent:

[{
  id: 5,
  name: 'b',
  children: [...]
}]

I'm looking to replicate a "breadcrumb" navigation

Upvotes: 1

Views: 650

Answers (4)

StepUp
StepUp

Reputation: 38199

The Depth First Search Algorithm - get parent node is:

function getParentNodeByKey(obj, targetId, paramKey) {
    if (obj.children) {
        if (obj.children.some(ch => ch[paramKey] === targetId))
            return obj;
        else {
            for (let item of obj.children) {
                let check = this.getParentNodeByKey(item, targetId, paramKey)
                if (check) {
                    return check;
                }
            }
        }
    }
    return null
}

and code to test:

var arr = [{
    id: 2,
    name: 'a',
    children: []
  }, {
    id: 5,
    name: 'b',
    children: [{
      id: 14,
      name: 'b2'
    }]

  }, {
    id: 15,
    name: 'd',
    children: []
}];

let parentElement;
const valueToFind = 14;
const desiredkey = 'id';
for (let i = 0; i < arr.length; i++) {
    parentElement = getParentNodeByKey(arr[i], valueToFind, desiredkey);
    if(parentElement)
        break;
}

console.log(`The parent element is:`, parentElement);

Upvotes: 1

Aphrem Thomas
Aphrem Thomas

Reputation: 263

You can try this way,

     var arr = [{
          id: 2,
          name: 'a',
          children: []
        }, {
          id: 5,
          name: 'b',
          children: [{ 
            id: 14,
            name: 'b2'
          }]

        }, {
          id: 15,
          name: 'd',
          children: []
        }];


    function getAncestor(obj,id,ancestor){
     if(obj.id===id){
        console.log(ancestor);
     }
     else
        if(obj&& obj.children && obj.children.length)
            obj.children.forEach(item=>this.getAncestor(item,id,obj));
    }

arr.forEach(o=>getAncestor(o,14,{}));

Upvotes: 1

Nina Scholz
Nina Scholz

Reputation: 386766

You could handover an object which is the parent and search recursive for the wanted id.

function getParent(object, id) {
    var result;
    (object.children || []).some(o => result = o.id === id ? object : getParent(o, id));
    return result;
}

var array = [{ id: 2, name: 'a', children: [] }, { id: 5, name: 'b', children: [{  id: 14, name: 'b2' }] }, { id: 15, name: 'd', children: [] }];

console.log(getParent({ children: array }, 14));
.as-console-wrapper { max-height: 100% !important; top: 0; }

If you like to hand over the array, you could take a nested approach with recursive function.

function getParent(children, id) {

    function iter(object) {
        var result;
        (object.children || []).some(o => result = o.id === id ? object : iter(o));
        return result;
    }

    return iter({ children });
}

var array = [{ id: 2, name: 'a', children: [] }, { id: 5, name: 'b', children: [{  id: 14, name: 'b2' }] }, { id: 15, name: 'd', children: [] }];

console.log(getParent(array, 14));
.as-console-wrapper { max-height: 100% !important; top: 0; }

Upvotes: 2

SparkFountain
SparkFountain

Reputation: 2270

If we can assume that only two levels exist (parents and children, not children of children) then the following function findAncestor() does what you need. It iterates over all parent elements and checks if they have a child with the relevant ID.

function findAncestor(id) {
  for (let i = 0; i < arr.length; i++) {
    let obj = arr[i];
    if (obj.hasOwnProperty('children')) {
      if (obj.children.length > 0) {
        for (let j = 0; j < obj.children.length; j++) {
          if (obj.children[j].id === id) {
            return obj;
          }
        }
      }
    }
  }

  return null;
}

console.info(findAncestor(14));

If you need to handle the case that a child with same ID can occur in several parents, you should use a result array and add all found results to it before returning it in the end.

Upvotes: 1

Related Questions