Reputation: 4244
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:
4
, return [2, 3]
.3
, return [2]
.8
, return [6, 7]
.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.
Upvotes: 1
Views: 2583
Reputation: 3580
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);
Upvotes: 3
Reputation: 545
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/
Upvotes: 0