How do I find all possible paths between a simple structure?

Question

I have a structure like this:

[
  {index: 1, children: [2]},
  {index: 2, children: [3, 4]}
  {index: 3, children: [4]}
  {index: 4, children: []}
]

and I wanna find all possible paths in this structure so I eventually get the longest one (I need to decide the max length of the whole trip). So in this structure the algorithm should export something like

[[1, 2, 3, 4], [1, 2, 4]]

or just the final answer which is 4 (the length of the longest trip). I found a few solutions online, at this point I am sure that this is only solvable with recursion but just can't figure it out. Any ideas of implementing this would be awesome, I am trying to solve this with js.

Answer 1

let input = [{ index: 1, children: [2] }, { index: 2, children: [3, 4] }, { index: 3, children: [4] }, { index: 4, children: [] }];

function find_all_possible_paths(nodes, key) {
  let result = [];
  function next(key, paths = [key]) {
    let node = nodes.find(v => v.index == key);

    if (node?.children.length)
      for (let index of node.children) {
        if (paths.includes(index)) throw new Error("Reference cycle error:\n" + JSON.stringify({ paths, node }, null, 4));
        next(index, paths.concat(index))
      }
    else result.push(paths)
  }
  next(key);
  return result
}

console.log(find_all_possible_paths(input, 1))