Q:

JavaScript - How can I return the branch of a tree in a node search?

My data structure will look like this:
var tree = [
    {
        id: 1,
        children: []
    }, {
        id: 2,
        children: [
            {
                id: 3,
                children: []
            }
        ]
    }
];

There can be any number of nodes or children on one branch.
My goal is to start at the top (root) node, search for a given node and return the branch it's on.
So in the example on Plunker: https://plnkr.co/edit/PyR3H7mM0vrFyno1l7R5?p=catalogue
I want to search for the node id # 31, so the algorithm will return the array (branch) that 31 is a part of.
I have started the algorithm but if I do it recursively I don't know how to backtrack out again.
function traverse(branch) {

  for (var i = 0; i < branch.length; i++) {
    if (branch[i].id == node.id) {
      return branch;
    }
  }

  for (var j = 0; j < branch.length; j++) {
    if (branch[j].children.length > 0) {
      return traverse(branch[j].children);
    }
  }

}

console.log(traverse(tree));

For example, if I look down to the last child node without finding a match then I need to backtrack to the parent branch to try the next set of options.
How can I modify my algorithm to backtrack out again?

A:

Your algorithm is very close, you just need to add an if statement so that it only returns the recursive result from traverse if a match was found:
function traverse(branch) {

  for (var i = 0; i < branch.length; i++) {
    if (branch[i].id == node.id) {
      return branch;
    }
  }

  for (var j = 0; j < branch.length; j++) {
    var result = traverse(branch[j].children);
    if (result !== undefined) {
      return result;
    }
  }

  return undefined; // no match found

}

console.log(traverse(tree));

