Recursively find arbitrary node path in tree

Question

I have a tree of objects composed with the following structure:

interface Node {
  name: string;
  children?: Node[];
}

Where, for example, { name: "foo", children: [ { name: "bar" } ] } is a valid tree. I'm trying to get the address of an arbitrary node, that can be a leaf, returned as an array of the path to arrive it, where the node will be compared by object reference. Example given, I have the following structure:

var data = {
  name: "Languages",
  children: [{
    name: "Functional",
    children: [
      { name: "OCaml" },
      { name: "Haskell" },
      { name: "Erlang" }
    ]
  }, {
    name: "Imperative",
    children: [
      { name: "BASIC" },
      { name: "Clipper" }
    ]
  }]
};

It is expected that, for example, if I have a reference for OCaml stored in a variable called ocaml that points exactly to that reference in memory, an array of steps be returned with the path to reach it, that would be, in this case, [0, 0].

I already can locate the object, but I'm not able to store the previous index, because this is non-deterministic:

var tree = function(struct, cmp) {
  if (struct.children) {
    var lookup = [];
    for (var i = 0; i < struct.children.length; i++) {
      lookup.push(tree(struct.children[i], cmp));
    }
    return lookup;
  } else {
    if (struct === cmp) {
      return "PASS";
    }
    return "FAIL";
  }
}

I can find the element, but how can I store the previous indexes to reach it from the base?

That doesn't look like your function does what you're trying to do at all. What is the output of this function? — Amit
– Amit, Commented Aug 24, 2015 at 16:44
I'll have an array containing other arrays as nodes and each leaf is either "PASS" or "FAIL", thus I can find the element, but I can't find the indexes to reach it, because this is non-deterministic and I don't know how I could store the previous indexes and discard the unmatched. — Marcelo Camargo
– Marcelo Camargo, Commented Aug 24, 2015 at 16:47
Just store pointer to parent node in every child, like interface Node { parent: Node; name: string; ...} — ankhzet
– ankhzet, Commented Aug 24, 2015 at 17:00
I did it. Now, I'm doing a linear search from leaf to base. I think it can solve. — Marcelo Camargo
– Marcelo Camargo, Commented Aug 24, 2015 at 17:02

David Conneely · Accepted Answer · 2015-08-24 17:51:03Z

Trying to keep track of the path in a locally-scoped variable won't work as each recursive call creates a new scope. Assuming you want something very similar what you have already, a fairly small change is to make the lookup path of indices be the return value from the method. The base case of the recursive call (when there are no child nodes) returns [] (found) or null (not found).

var tree = function(struct, cmp) {
    if (struct === cmp) {
        // `cmp` is found at current `struct`.
        return [];
    } else if (struct.children) {
        for (var i = 0; i < struct.children.length; i++) {
            var path = tree(struct.children[i], cmp);
            if (path !== null) {
                // `cmp` is found at `path` in `struct.children[i]`,
                // so prefix `i` to `path` to get the path in `struct`.
                path.unshift(i);
                return path;
            }        
        }
    }
    // `cmp` not found in this branch of the tree.
    return null;
};

console.log(tree(data, data.children[0].children[0])); // outputs [0, 0]
console.log(tree(data, data.children[0].children[2])); // outputs [0, 2]
console.log(tree(data, data.children[1].children[1])); // outputs [1, 1]

Nina Scholz · Accepted Answer · 2015-08-24 17:32:12Z

I wrapped the data in an array. For all nodes, you may store the references in an object like

var lookUp = {
    'OCaml':getNode(data, 'OCaml'),
    'BASIC': getNode(data, 'BASIC')
};

Or you can build the reference with a walk through the object.

var data = [{
    name: "Languages",
    children: [{
        name: "Functional",
        children: [
          { name: "OCaml" },
          { name: "Haskell" },
          { name: "Erlang" }
        ]
    }, {
        name: "Imperative",
        children: [
          { name: "BASIC" },
          { name: "Clipper" }
        ]
    }]
}];

function getNode(array, name) {

    function findNode(a, i, o) {
        if (a.name === name) {
            node = o[i]
            return true;
        }
        return Array.isArray(a.children) && a.children.some(findNode);
    }

    var node;
    array.some(findNode);
    return node;
}

var lookUp = {
    'OCaml':getNode(data, 'OCaml'),
    'BASIC': getNode(data, 'BASIC')
};

lookUp.BASIC.name = 'Basic';
document.write('<pre>' + JSON.stringify(data, 0, 4) + '</pre>');

Collectives™ on Stack Overflow

Recursively find arbitrary node path in tree

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