LeetCode 133 Clone Graph - Implementation

Here's the complete implementation:

function cloneGraph(node):
    if node is null:
        return null

    old_to_new = empty map

    function dfs(original):
        if original in old_to_new:
            return old_to_new[original]

        copy = new Node(original.val)
        old_to_new[original] = copy

        for each neighbor in original.neighbors:
            copy.neighbors.append(dfs(neighbor))

        return copy

    return dfs(node)

Time: $O(N + E)$ where N is nodes and E is edges. Space: $O(N)$ for the map and recursion stack.