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.

## Advertisement

## 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)))