CloneGraphDFSUsingStack.java

// exactly the same as BFS except used a stack to mimic the recursion, technically any BFS can be written
// in DFS by using a stack
public Node cloneGraphDFSUsingStack(Node node) {
    if (node == null) {
        return node;
    }
    Map<Node, Node> lookup = new HashMap<>();
    Node t = new Node(node.val, new ArrayList<>());
    lookup.put(node, t);

    Stack<Node> stack = new Stack<>();
    stack.push(node);

    while (!stack.isEmpty()) {
        Node cur = stack.pop();

        for (Node n : cur.neighbors) {
            Node copiedNeighbor = null;
            if (!lookup.containsKey(n)) {
                copiedNeighbor = new Node(n.val, new ArrayList<>());
                stack.push(n);
                lookup.put(n, copiedNeighbor);
            } else {
                copiedNeighbor = lookup.get(n);
            }
            lookup.get(cur).neighbors.add(copiedNeighbor);
        }
    }

    return lookup.get(node);
}