Leetcode: Clone Graph

This question is asked extremely commonly at Facebook, Amazon, and Microsoft.

You are given a reference of a node in a connected undirected graph, and each node in the graph. We want to return a deep copy of the graph. 

Each node contains a value and a list of its neighbors. 

class Node {

    public int val;

    public List<Node> neighbors; 

}

Here's the Test Case format: 

Adjacency list is a collection of unordered lists used to represent a finite graph, and the given node will always be the first node with val = 1, and must return the cope of the given node as a reference to the cloned graph. Makes no sense so far, but let's move on. 

We can use DFS and BFS for this problem. This is an undirected graph, meaning that each graph is connected both ways. As we traverse through every input, we want to make copies of each node. The way we know which copy will be a map where the key will be the integer and the value will be the new copy node. It returns the copy if it has not been created. 

class Solution {

    public Node cloneGraph(Node node) {

           if(node == null) return null;

            Map<Integer, Node> map = new HashMap<>();

             //call the helper method. 

             return cloneGraph(node, map);

    }

     private Node cloneGraph(Node node, Map<Integer, Node> map) {

        //"backtrack" if the map contains the key of the Node.

        if(map.containsKey(node.val)) return map.get(node.val);

        Node copy = new Node(node.val); 

         //add the node inside of the map

        map.put(node.val, copy);

        for(Node neighbor : node.neighbors) {

              //add the neighbors for this node, recursively by going downwards first and then upwards (DFS). 

               copy.neighbors.add(cloneGraph(neighbor, map)); 

         }

        return copy;

    }

}