user687554 user687554 - 13 days ago 6
jQuery Question

JavaScript - Recursively Finding Parent Nodes

I have an app written with JavaScript. In this app, I have a tree of JavaScript objects. An example tree and the code below can be seen in this JSFiddle.

I am trying to write a function that will return a list of IDs that are the ancestors. The ancestors of a element with a specific ID. Currently, I have the following:

function getAncestors(childId, branch) {
var ancestors = [];
for (var i = 0; i < branch.length; i++) {
for (var j = 0; j < branch[i].children.length; j++) {
if (branch[i].children[j].id === childId) {
ancestors.push(branch[i].id);
return ancestors;
} else {
var _ancestors = getAncestors(childId, branch[i].children);
for (var k = 0; k < _ancestors.length; k++) {
if (ancestors.indexOf(_ancestors[k]) === -1) {
ancestors.push(_ancestors[k]);
}
}
}
}
}
return ancestors;
}


It always returns the first parent. However, it doesn't return all ancestors. For example, in the JSFiddle, I'm trying to get an array that contains: [201, 2], in that order. I'm not sure what I'm doing incorrectly though. I keep staring at this and it looks correct. But, obviously, it's not working.

Answer

Here is working code (using iteration):

function getAncestors(childId, newbranch) {
    for (var i = 0; i < newbranch.length; i++) { // Search all branches
        var branch = newbranch[i];

        if (branch.id === childId) {
            return [];
        } else {
            if (branch.children && branch.children.length) {
                var x;

                if ((x = getAncestors(childId, branch.children)) !== false) {
                    x.push(branch.id)
                    return x;
                }
            }
        }
    }

    return false;
}

Result:

[201,2]

Edit (shorter)

function getAncestors(childId, branch) {
    var i, ancestors;

    for (i = 0; !ancestors && branch && i < branch.length; i++) {
        if (branch[i].id === childId) return [];
        ancestors = getAncestors(childId, branch[i].children);
        if (ancestors) ancestors.push(branch[i].id);
    }
    return ancestors;
}
Comments