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

Scott’s answer is beautiful. I’m going to share an approach using generators because often times problems like these involve only finding one or some known amount of solutions. Generators allow us to stop computation early instead of computing all routes. Notice the similarity between the structure of the generator approach and Scott’s program –

function* routes ({departureAirportId, flights = []}, r = [])
{ if (flights.length === 0)
    yield [...r, departureAirportId]
  else
    for (const q of flights) 
      yield* routes(q, [...r, departureAirportId])
}

function* endingAt (t, loc)
{ for (const r of routes(t))
    if(r[r.length - 1] == loc)
      yield r
}

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(Array.from(endingAt(flightsTree, 2)))

The above approach is sound because it decomposes the problem into two separate parts, routes and endingAt. However the two functions can be collapsed into one, if you wish –

function* endingAt (t, loc, r = [])
{ if (t.flights)
    for (const q of t.flights) 
      yield* endingAt(q, loc, [...r, t.departureAirportId])
  else if (t.departureAirportId == loc)
    yield [...r, t.departureAirportId]
}

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(Array.from(endingAt(flightsTree, 2)))


Source: stackoverflow