/**
* // Definition for a Node.
* function Node(val, neighbors) {
*    this.val = val === undefined ? 0 : val;
*    this.neighbors = neighbors === undefined ? [] : neighbors;
* };
*/

/**
* @param {Node} node
* @return {Node}
*/
// DFS Hashmap Approach
// O(N + M) time, O(N) space
var cloneGraph = function(node) {
 // Base case if node is null, we return back null
 if (node === null) {
   return null;
 }
 
 // Keep track of a visited hashmap of unique node values to cloned nodes
 const visited = new Map();
 
 // DFS to clone each node as we go and mark as visited along the way
 const dfs = (root) => {
   // If the current root is already visited, return the cloned node
   if (visited.has(root.val)) {
     return visited.get(root.val);
   }
   
   // Clone node and mark it as visited
   const clonedNode = new Node(root.val);
   visited.set(root.val, clonedNode);
   
   // Loop through each neighbor and add it to cloned list of neighbors
   const clonedNeighbors = [];
   root.neighbors.forEach((neighbor) => {
     clonedNeighbors.push(dfs(neighbor));
   });
   
   // Add cloned list of neighbors to cloned node
   clonedNode.neighbors = clonedNeighbors;
   
   // Return the current root
   return clonedNode;
 };
 
 return dfs(node);
};