Print path from root to a given node in a tree with multiple children

I am trying to print the path from root to a given node containing value of 2. Each node can have children containing several nodes. Here is a visual reference

I have flight data like this:

const flightsTree = {
  departureAirportId: 1,
  flights: [
    {
      departureAirportId: 16,
      flights: [
        { departureAirportId: 8 },
        { departureAirportId: 17 },
        { departureAirportId: 2 },
        { departureAirportId: 11 },
        {
          departureAirportId: 10,
          flights: [
            {
              departureAirportId: 17,
              flights: [{ departureAirportId: 99 }, { departureAirportId: 2 }],
            },
            { departureAirportId: 2 },
          ],
        },
        { departureAirportId: 2 },
        { departureAirportId: 6 },
        { departureAirportId: 3 },
      ],
    },
  ],
};

This is the code I wrote so far:

const hasPath = (data, path, from) => {
  if (!data) {
    return false;
  }
  path.push(data.departureAirportId);
  if (data.departureAirportId === from) {
    return true;
  }
  if (data.flights) {
    data.flights.forEach((pRule) => {
      hasPath(pRule, path, from);
      return true;
    });
  } else {
    path.pop();
    return false;
  }
  return path;
};

console.log(hasPath(flightsTree, [], 2));

So far I’m getting:

[1, 16, 2, 10, 17, 2, 2, 2]

It seems like it is able to find the node containing the value but not to print the root path except for the first finding.

Thanks a lot for your help.

Answer

This version first calculates all routes and then filter for those that end with the given location. The second part is trivial. The first is a simple recursion; when the route has no flights, we simply return an array consisting of an array holding the departure airport. When it has flights, we recur on those and to each of the results, we prepend our current departure airport:

const routes = ({departureAirportId, flights = []}) => 
  flights.length == 0
    ? [[departureAirportId]]
    : flights .flatMap (routes) .map (r => [departureAirportId, ...r])

const endingAt = (loc, flights) => 
  routes (flights) .filter (r => r [r.length - 1] == loc)

const flightsTree = {departureAirportId: 1, flights: [{departureAirportId: 16, flights: [{departureAirportId: 8}, {departureAirportId: 17}, {departureAirportId: 2}, {departureAirportId: 11}, {departureAirportId: 10, flights: [{departureAirportId: 17, flights: [{departureAirportId: 99}, {departureAirportId: 2}]}, {departureAirportId: 2}]}, {departureAirportId: 2}, {departureAirportId: 6}, {departureAirportId: 3}]}]}

console .log (endingAt (2, flightsTree))

.as-console-wrapper {max-height: 100% !important; top: 0}

There are two assumptions here. The first is that you want only those that end at the target airport. If you want all paths that go through airport 2, you can replace endingAt with a function that filters the routes testing if any contain the target.

The second is that the order of the results is not that important. This depth-first traversal is simpler, but if the order of the results in your image is important, we can certainly write a breadth-first traversal version.