CODEWITHSUNDEEP
javascriptjquery
user687554
user687554

Reputation: 11131

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.

Upvotes: 3

Views: 154

Answers (2)

Francesco
Francesco

Reputation: 555

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

Upvotes: 2

Nina Scholz
Nina Scholz

Reputation: 386519

You could use an iterative and recursive approach with a callback for Array#some and the actual parents.

function getParents(id, array) {
    function iter(parents) {
        return function (a) {
            if (a.id === id) {
                result = parents;
                return true;
            }
            return a.children && a.children.some(iter([a.id].concat(parents)));
        };
    }

    var result;
    array.some(iter([]));
    return result;
}

var tree = [{ id: 1, name: 'Left', children: [{ id: 100, name: 'C1', children: [{ id: 1000, name: 'C2A', children: [] }, { id: 1001, name: 'D2A', children: [] }, { id: 1002, name: 'C2B', children: [] }] }, { id: 101, name: 'C2', children: [{ id: 2000, name: 'D7B', children: [] }, { id: 2001, name: 'E2A', children: [] }, { id: 2002, name: 'C2X', children: [] }] }] }, { id: 2, name: 'Middle', children: [{ id: 200, name: 'Z1', children: [{ id: 3000, name: 'R2A', children: [] }, { id: 3001, name: 'DYA', children: [] }, { id: 3002, name: 'Q2B', children: [] }] }, { id: 201, name: 'X2', children: [{ id: 4000, name: 'DMA', children: [] }, { id: 4001, name: 'ELA', children: [] }, { id: 4002, name: 'CRX', children: [] }] }] }, { id: 3, name: 'Right', children: [{ id: 300, name: 'Z1', children: [{ id: 5000, name: 'F7A', children: [] }, { id: 5001, name: 'EW5', children: [] }, { id: 5002, name: 'D5B', children: [] }] }, { id: 301, name: 'X2', children: [{ id: 6000, name: 'OMA', children: [] }, { id: 6001, name: 'NLA', children: [] }, { id: 6002, name: 'MRX', children: [] }] }] }];

console.log(getParents(4001, tree));

Version without moving an array, but with a marker for the actual depth. The result is now reversed.

function getParents(id, array) {
    function iter(depth) {
        return function (a) {
            result[depth] = a.id;
            if (a.id === id) {
                result.length = depth;
                return true;
            }
            return a.children && a.children.some(iter(depth + 1));
        };
    }

    var result = [];
    return array.some(iter(0)) && result;
}

var tree = [{ id: 1, name: 'Left', children: [{ id: 100, name: 'C1', children: [{ id: 1000, name: 'C2A', children: [] }, { id: 1001, name: 'D2A', children: [] }, { id: 1002, name: 'C2B', children: [] }] }, { id: 101, name: 'C2', children: [{ id: 2000, name: 'D7B', children: [] }, { id: 2001, name: 'E2A', children: [] }, { id: 2002, name: 'C2X', children: [] }] }] }, { id: 2, name: 'Middle', children: [{ id: 200, name: 'Z1', children: [{ id: 3000, name: 'R2A', children: [] }, { id: 3001, name: 'DYA', children: [] }, { id: 3002, name: 'Q2B', children: [] }] }, { id: 201, name: 'X2', children: [{ id: 4000, name: 'DMA', children: [] }, { id: 4001, name: 'ELA', children: [] }, { id: 4002, name: 'CRX', children: [] }] }] }, { id: 3, name: 'Right', children: [{ id: 300, name: 'Z1', children: [{ id: 5000, name: 'F7A', children: [] }, { id: 5001, name: 'EW5', children: [] }, { id: 5002, name: 'D5B', children: [] }] }, { id: 301, name: 'X2', children: [{ id: 6000, name: 'OMA', children: [] }, { id: 6001, name: 'NLA', children: [] }, { id: 6002, name: 'MRX', children: [] }] }] }];

console.log(getParents(4001, tree));

Upvotes: 2

Related Questions