Finding parent objects in nested arrays of objects. How?

Question

I have a data structure that looks like this:

var someDataStructure = [
  {
    opts: {_id:1}
  },
  {
    opts: {_id: 2},
    children: [
      {
        opts: {_id: 3},
        children: [
          {
            opts: {_id: 4}
          }
        ]
      }
    ]
  },
  {
    opts: {_id: 5}
  },
  {
    opts: {_id: 6},
    children: [
      {
        opts: {_id: 7},
        children: [
          {
            opts: {_id: 8}
          }
        ]
      }
    ]
  }  
];

That's an array of objects, all with an opts property, and an optional children property. If it exists the children property will be an array of the same sort of objects.

Given any opts._id, I need to find the _id of all parent objects. The _id's I give here are only sequential for convenience. You may not assume they are sequential integers

This project is using both jquery and lodash so both of those libraries are available for use.

Example desired output:

Given 4, return [2, 3].
Given 3, return [2].
Given 8, return [6, 7].
Given 7, return [6].

I have no problem recursing in and finding the given _id. However, I'm feeling dumb and stuck on maintaining the array of parents.

@Linus sorry, fixed desired output. That's what I get for doing too much editing and not enough proofreading. — Dustin Wyatt
– Dustin Wyatt, Commented Dec 14, 2014 at 1:41

Linus · Accepted Answer · 2014-12-14 03:18:43Z

A solution returning found status and parents if found.

function getParentsHelper(tree, id, parents) {
    if (tree.opts._id == id) {
        return {
            found: true,
            parents: parents
        };
    }
    var result = {
        found: false,
    }
    if (tree.children) {
        $.each(tree.children, function(index, subtree) {
            var maybeParents = $.merge([], parents);
            if (tree.opts._id != undefined) {
                maybeParents.push(tree.opts._id);
            }
            var maybeResult = getParentsHelper(subtree, id, maybeParents);
            if (maybeResult.found) {
                result = maybeResult;
                return false;
            }
        });
    }
    return result;
}

function getParents(data, id) {
    var tree = {
        opts: { },
        children: data
    }
    return getParentsHelper(tree, id, []);
}

Usage example:

console.log(getParents(someDataStructure, 4).parents);
console.log(getParents(someDataStructure, 3).parents);
console.log(getParents(someDataStructure, 8).parents);
console.log(getParents(someDataStructure, 7).parents);

Alessandro Marchisio · Accepted Answer · 2014-12-14 01:36:00Z

0

for one children this works:

function writeParent(id, arr) {

    var ct = 0;
    var found = false;
    var parentsLine = []; 

    arr.some(function (e){
        parentsLine = []

        for (var curr = e; curr.children != null; curr = curr.children[0]) {
            if (id == curr.opts._id) {
                found = true;
                return true;
            } 
            parentsLine.push(curr.opts._id)    

        }  

        if (id == curr.opts._id) {
            found = true;
            return true;
        } 


    })
    if (found) {
        return parentsLine;
    } else {
        return "ERR: elm not found";
    }    
}

see http://jsfiddle.net/alemarch/ufrLpLfx/11/

answered Dec 14, 2014 at 1:36

Alessandro Marchisio

5453 silver badges12 bronze badges

Collectives™ on Stack Overflow

Finding parent objects in nested arrays of objects. How?

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related