I've got a data structure that looks something like this:

let tree = {
  id: 1,
  name: "Some Name",
  children: [
    {
      id: 2,
      name: "Child 1",
      children: [...more nested objects...]
    }
  ]
};

I've written a recursive function to find a given object within that tree, but I now need to also return the path through the tree to the object that is returned. I'm trying to figure out how to modify my search function to do this.

Search function:

_findInTree = (id, tree) => {
    let result;
    if (tree.id === id) {
      result = tree;
    } else {
      for (let child of tree.children) {
        if (child.id === id) { result = child; }
        result = this._findInTree(id, child);
        if (result) { break; }
      }
    }
    return result;
  }

I've got a data structure that looks something like this:

let tree = {
  id: 1,
  name: "Some Name",
  children: [
    {
      id: 2,
      name: "Child 1",
      children: [...more nested objects...]
    }
  ]
};

I've written a recursive function to find a given object within that tree, but I now need to also return the path through the tree to the object that is returned. I'm trying to figure out how to modify my search function to do this.

Search function:

_findInTree = (id, tree) => {
    let result;
    if (tree.id === id) {
      result = tree;
    } else {
      for (let child of tree.children) {
        if (child.id === id) { result = child; }
        result = this._findInTree(id, child);
        if (result) { break; }
      }
    }
    return result;
  }

• javascript
• tree

Share Improve this question Follow edited Oct 3, 2018 at 2:40 Machavity♦ 31.7k2727 gold badges9595 silver badges105105 bronze badges asked Jul 15, 2015 at 12:26 Kevin WhitakerKevin Whitaker 13.5k1313 gold badges5454 silver badges9494 bronze badges

Add a ment  | 

3 Answers 3

Sorted by: Reset to default 5

You'll need the array index, so you can either track it outside the for-of and then use it on the path, or use Array#some instead (or use a boring old for).

Here's tracking the index outside the for-of — I also added an else I think was probably pretty important: :-)

_findInTree = (id, tree, path = "") => {
    let result;
    let index;
    let rv;
    if (tree.id === id) {
        result = tree;
    } else {
        index = 0;
        for (let child of tree.children) {
            if (child.id === id) {
                result = child;
                break;
            }
            rv = this._findInTree(id, child, path + "[" + index + "]");
            if (rv != null) {
                return rv;
            }
            ++index;
        }
    }
    return { result, path };
};

Obviously, adjust the format of path as you see fit. (Doesn't have to be a string, for instance, could be an array.)

Here's the some solution:

_findInTree = (id, tree, path = "") => {
    let result;
    let rv = null;
    if (tree.id === id) {
        result = tree;
    } else {
        tree.children.some((child, index) => {
            if (child.id === id) {
                result = child;
                return true;
            }
            rv = this._findInTree(id, child, path + "[" + index + "]");
            if (rv) {
                return true;
            }
        });
    }
    return rv || { result, path };
};

So T.J. Crowders position ended up having a bug around recording the path, and I ended up tweaking the solution to get the following, which works excellently.

  _findInTree(id, tree) {
    if (tree.id === id) {
      let path = [tree.name];
      return {result: tree, path};
    } else {
      for (let child of tree.children) {
        let tmp = this._findInTree(id, child);
        if (!_.isEmpty(tmp)) {
          tmp.path.unshift(tree.name);
          return tmp;
        }
      }
      return {};
    }
  }

As For me, I need to change Kevin Whitaker code to this one

_findInTree(id, tree) {
    if (tree.id === id) {
      let path = [tree.name];
      return {result: tree, path};
    } else if (tree.children) { //THIS IS THE CHANGES THAT I NEED
      for (let child of tree.children) {
        let tmp = this._findInTree(id, child);
        if (!_.isEmpty(tmp)) {
          tmp.path.unshift(tree.name);
          return tmp;
        }
      }
      return {};
    }
  }