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.

• Alessandro Marchisio: each opts can have only one children?
• Linus: Are you sure those examples of desired output are correct?
• Alessandro Marchisio: Gives 8 return [6,7]; gives 2 return []
• Dustin Wyatt: @Linus sorry, fixed desired output. That's what I get for doing too much editing and not enough proofreading.
• Dustin Wyatt: @AlessandroMarchisio children can be nested to any depth.

Answer 1

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);

Answer 2

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/