1
function dfs(edges, s = `JFK`, ans = [`JFK`]) {
2
  //run dfs, starting node being `JFK`
3
  if (!edges[s] || edges[s].length == 0) {
4
    //if currenctly reached node has its adjacent list empty
5
    let isAllTravelled = 1;
6
    Object.values(edges).forEach((ele) => {
7
      if (ele.length > 0) isAllTravelled = 0;
8
    }); // check if every edge has been travelled i.e all adjacentLists should be empty
9
    if (!isAllTravelled)
10
      return false; //returns false when there are more edges to travel , but from current node we cannot move anywhere else
11
    else return ans; // return true if from current node we cannot move anywhere else and all the edges have been travelled as well
12
  }
13

14
  let myAL = edges[s].sort(); // sort the Adjacency List  of current node lexicographically
15
  for (let i = 0; i < myAL.length; i++) {
16
    // start by taking the lexicographically smallest node and run dfs
17
    ans.push(myAL[i]); // add current node into answer array
18
    edges[s] = [
19
      ...edges[s].slice(0, edges[s].indexOf(myAL[i])),
20
      ...edges[s].slice(edges[s].indexOf(myAL[i]) + 1),
21
    ]; // remove the currently edges travelled from adjacency List
22
    let xx = dfs(edges, myAL[i], ans); //here runs the dfs
23
    if (!xx) {
24
      // if dfs result of current node could not travel all edges from current node
25
      ans.pop(); // pop out current accounted node from answer
26
      edges[s].push(myAL[i]); //put back the edge into adjacency list assmuing we should not visit this edge at this point as it doesnt leads to answer from here currenlt
27
    } else return xx; // if dfs result of current node could travel all edges from current node return the answer array
28
  }
29
}
30
var findItinerary = function (tickets) {
31
  let edges = {}; //our adjacency list
32
  tickets.forEach((ticket) => {
33
    if (!edges[ticket[0]]) {
34
      edges[ticket[0]] = [];
35
    }
36
    edges[ticket[0]].push(ticket[1]);
37
  });
38

39
  let ans = dfs(edges); // run dfs
40
  return ans;
41
};