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

user_13761875 0
Viewed 349

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.

traversal tree recursion javascript
2 Answers

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.

user_12436410

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

user_6331830
Related