• Leetcode 133
• Difficulty: Medium
• Patterns:
  • Breadth-First Search
  • Depth-First Search

---

Problem Definition

---

Node Class

The Node class that will be represent every node in the graph:

class Node:
    def __init__(self, val: int, neighbors: list['Node'] = []):
        self.val = val
        self.neighbors = neighbors

---

Examples

Some test cases to verify our solution. Here, we'll test manually by printing neighbors.

# 1----2
# |    |
# 3----4
one = Node(1)
two = Node(2)
three = Node(3)
four = Node(4)
one.neighbors = [two, three]
two.neighbors = [one, four]
three.neighbors = [one, four]
four.neighbors = [two, three]

res = clone(one)
stack = [res]
visited = set([res])
while stack:
    n = stack.pop()
    print("val: {val}, neighbors:[{neighbors}]".format(
        val=n.val, neighbors=", ".join(str(nxt.val) for nxt in n.neighbors)
    ))
    for nxt in n.neighbors:
        if nxt not in visited:
            visited.add(nxt)
            stack.append(nxt)

---

Solution

This is a graph traversal problem; so we can solve it using a depth-first traversal or a breadth-first traversal. Here, we implement a DFS solution.

During traversal, we'll mark each node as visited so we don't end up in loops.

def clone(node: Node) -> Node:
    if Node is None:
        return None
    ans = Node(val=node.val, neighbors=[])
    node_to_copy = {node: ans}
    stack = [n for n in node.neighbors]
    visited = set(stack)
    visited.add(node)
    while stack:
        n = stack.pop()
        copy = Node(val=n.val, neighbors=[])
        node_to_copy[n] = copy
        for nxt in n.neighbors:
            if nxt not in visited:
                stack.append(nxt)
                visited.add(nxt)
    stack = [node]
    visited = set(stack)
    while stack:
        n = stack.pop()
        copy = node_to_copy[n]
        for nxt in n.neighbors:
            if nxt not in visited:
                stack.append(nxt)
                visited.add(nxt)
            copy.neighbors.append(node_to_copy[nxt])
    return ans

---

Complexity

Let $n = $ the number of nodes in the graph.

Since we are visiting every node twice, the runtime complexity should be $\Theta(n)$.

Auxiliary space complexity should be $\Theta(n)$ since we are storing a visited set of nodes.