Clone Graph, Valid Tree, and Graph Transformations

Graph transformation problems ask you to build, copy, or reshape a graph structure. These problems test your understanding of graph representations and traversal at a deeper level than simple reachability questions.

Problem 1: Clone Graph (LeetCode 133)

Problem: Given a reference to a node in a connected undirected graph, return a deep copy of the graph. Each node has a value and a list of neighbors.

The challenge: nodes reference each other, so a naive recursive copy would loop forever. The solution is to track which nodes have already been cloned using a hash map.

Node definition

class Node:
    def __init__(self, val=0, neighbors=None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []

DFS approach

def clone_graph_dfs(node: 'Node') -> 'Node':
    """
    LeetCode 133: Clone Graph using DFS.
    """
    if not node:
        return None

    cloned = {}   # original node -> cloned node

    def dfs(original: 'Node') -> 'Node':
        if original in cloned:
            return cloned[original]

        copy = Node(original.val)
        cloned[original] = copy

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

        return copy

    return dfs(node)

How it works:

1. When visiting a node for the first time, create its clone and store the mapping in cloned.
2. Recursively clone each neighbor.
3. If a neighbor was already cloned (cycle detected), return the existing clone from the map instead of creating a new one.

BFS approach

from collections import deque

def clone_graph_bfs(node: 'Node') -> 'Node':
    """
    LeetCode 133: Clone Graph using BFS.
    """
    if not node:
        return None

    cloned = {node: Node(node.val)}
    queue = deque([node])

    while queue:
        original = queue.popleft()

        for neighbor in original.neighbors:
            if neighbor not in cloned:
                cloned[neighbor] = Node(neighbor.val)
                queue.append(neighbor)

            cloned[original].neighbors.append(cloned[neighbor])

    return cloned[node]

Time: O(V + E) — visit each node and edge once.

Space: O(V) for the hash map and queue/stack.

Why the hash map is essential

Without it, you would either:

• Clone the same node multiple times (wrong: clones would not share references correctly).
• Enter an infinite loop on cycles.

The hash map serves dual duty: it is both a “visited” set and a mapping from original to clone.

Walkthrough

Consider a graph: 1 — 2 — 3, 1 — 3

DFS from node 1:

1. Create clone of 1. cloned = {1: 1'}
2. Visit neighbor 2. Create clone of 2. cloned = {1: 1', 2: 2'}
3. Visit neighbor 3 (from 2). Create clone of 3. cloned = {1: 1', 2: 2', 3: 3'}
4. Visit neighbor 1 (from 3). Already cloned, return 1’.
5. Visit neighbor 2 (from 3). Already cloned, return 2’.
6. Back to 1, visit neighbor 3. Already cloned, return 3’.

Result: perfect deep copy with all references intact.

Problem 2: Graph Valid Tree (LeetCode 261)

Problem: Given n nodes labeled 0 to n-1 and a list of undirected edges, determine if these edges form a valid tree.

A valid tree must satisfy two conditions:

1. Connected: all nodes are reachable from any starting node.
2. Acyclic: exactly n - 1 edges (for n nodes).

Quick check + BFS

from collections import deque, defaultdict

def valid_tree(n: int, edges: list[list[int]]) -> bool:
    """
    LeetCode 261: Graph Valid Tree.
    """
    # A tree with n nodes has exactly n-1 edges
    if len(edges) != n - 1:
        return False

    # Build adjacency list
    adj = defaultdict(list)
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)

    # BFS to check connectivity
    visited = set([0])
    queue = deque([0])

    while queue:
        node = queue.popleft()
        for neighbor in adj[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

    return len(visited) == n

Why n - 1 edges is sufficient: A connected graph with exactly n - 1 edges cannot have a cycle (adding any edge to a tree creates exactly one cycle). So checking edge count + connectivity is enough. If we have fewer than n - 1 edges, the graph is disconnected. If we have more, it must contain a cycle.

Union-Find approach

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False     # cycle detected
        if self.rank[rx] < self.rank[ry]:
            rx, ry = ry, rx
        self.parent[ry] = rx
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1
        return True


def valid_tree_uf(n: int, edges: list[list[int]]) -> bool:
    """
    Graph Valid Tree using Union-Find.
    """
    if len(edges) != n - 1:
        return False

    dsu = DSU(n)
    for u, v in edges:
        if not dsu.union(u, v):
            return False     # cycle found

    return True

Time: O(E * alpha(V)) which is effectively O(E).

Space: O(V)

DFS cycle detection alternative

def valid_tree_dfs(n: int, edges: list[list[int]]) -> bool:
    """Graph Valid Tree using DFS cycle detection."""
    if len(edges) != n - 1:
        return False

    adj = defaultdict(list)
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)

    visited = set()

    def dfs(node: int, parent: int) -> bool:
        visited.add(node)
        for neighbor in adj[node]:
            if neighbor == parent:
                continue
            if neighbor in visited:
                return False  # cycle
            if not dfs(neighbor, node):
                return False
        return True

    if not dfs(0, -1):
        return False

    return len(visited) == n

Problem 3: Minimum Height Trees (LeetCode 310)

Problem: Given a tree of n nodes, find all roots that minimize the height of the tree. These roots are the centroids of the tree.

Key insight: peel leaves layer by layer

The centroid(s) of a tree can be found by repeatedly removing leaf nodes (nodes with degree 1) from the outside in, like peeling an onion. The last remaining 1 or 2 nodes are the centroids.

from collections import defaultdict, deque

def find_min_height_trees(n: int, edges: list[list[int]]) -> list[int]:
    """
    LeetCode 310: Minimum Height Trees.
    Returns list of root labels that produce minimum height trees.
    """
    if n == 1:
        return [0]
    if n == 2:
        return [0, 1]

    # Build adjacency list and track degrees
    adj = defaultdict(set)
    for u, v in edges:
        adj[u].add(v)
        adj[v].add(u)

    # Initialize with all leaves
    leaves = deque()
    for node in range(n):
        if len(adj[node]) == 1:
            leaves.append(node)

    remaining = n

    while remaining > 2:
        leaf_count = len(leaves)
        remaining -= leaf_count

        new_leaves = deque()
        for _ in range(leaf_count):
            leaf = leaves.popleft()
            # Each leaf has exactly one neighbor
            neighbor = adj[leaf].pop()
            adj[neighbor].remove(leaf)

            if len(adj[neighbor]) == 1:
                new_leaves.append(neighbor)

        leaves = new_leaves

    return list(leaves)

Time: O(V) — each node is processed exactly once.

Space: O(V) for adjacency list and queue.

Why at most 2 centroids?

A tree has either 1 or 2 centroids:

• Odd diameter: the middle node is the single centroid.
• Even diameter: the two middle nodes are both centroids.

You can never have 3 or more centroids because that would require three mutually equidistant nodes from the boundary, which is impossible in a tree (only one path exists between any two nodes).

Why leaf peeling works

Each round of leaf removal reduces the tree’s diameter by 2 (one from each end). The process converges to the center of the longest path (the diameter), which is exactly where the minimum height root(s) are.

Alternative: find the diameter endpoints

1. BFS from any node to find the farthest node u.
2. BFS from u to find the farthest node v and record the path.
3. The centroid is the middle of the path u -> v.

def find_mht_via_diameter(n: int, edges: list[list[int]]) -> list[int]:
    """Find MHT roots by finding the diameter path and taking the middle."""
    if n == 1:
        return [0]

    adj = defaultdict(list)
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)

    def bfs_farthest(start):
        visited = {start}
        queue = deque([(start, -1)])
        farthest = start
        parent = {start: -1}

        while queue:
            node, par = queue.popleft()
            farthest = node
            for neighbor in adj[node]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    parent[neighbor] = node
                    queue.append((neighbor, node))

        return farthest, parent

    # Find one end of the diameter
    u, _ = bfs_farthest(0)
    # Find the other end and the path
    v, parent = bfs_farthest(u)

    # Reconstruct the diameter path
    path = []
    node = v
    while node != -1:
        path.append(node)
        node = parent[node]

    mid = len(path) // 2
    if len(path) % 2 == 1:
        return [path[mid]]
    else:
        return sorted([path[mid - 1], path[mid]])

Problem 4: Reconstruct Itinerary (LeetCode 332)

Problem: Given a list of airline tickets [from, to], reconstruct the itinerary starting from "JFK". If multiple valid itineraries exist, return the one with the smallest lexicographic order. All tickets must be used exactly once.

This is an Eulerian path problem: find a path that uses every edge exactly once.

Hierholzer’s algorithm

Hierholzer’s algorithm finds an Eulerian circuit/path by greedily following edges and backtracking when stuck.

from collections import defaultdict

def find_itinerary(tickets: list[list[str]]) -> list[str]:
    """
    LeetCode 332: Reconstruct Itinerary.
    Uses Hierholzer's algorithm for Eulerian path.
    """
    # Build adjacency list sorted in reverse (so pop gives smallest)
    adj = defaultdict(list)
    for src, dst in sorted(tickets, reverse=True):
        adj[src].append(dst)

    route = []

    def dfs(airport: str):
        while adj[airport]:
            next_airport = adj[airport].pop()
            dfs(next_airport)
        route.append(airport)

    dfs("JFK")
    return route[::-1]

Why sort in reverse?

We use a list as a stack (pop from end). Sorting tickets in reverse lexicographic order means pop() gives the smallest destination first, ensuring we explore the lexicographically smallest path.

Iterative version

def find_itinerary_iterative(tickets: list[list[str]]) -> list[str]:
    """
    Iterative Hierholzer's algorithm.
    """
    adj = defaultdict(list)
    for src, dst in sorted(tickets, reverse=True):
        adj[src].append(dst)

    stack = ["JFK"]
    route = []

    while stack:
        while adj[stack[-1]]:
            stack.append(adj[stack[-1]].pop())
        route.append(stack.pop())

    return route[::-1]

Time: O(E log E) for sorting + O(E) for traversal.

Space: O(E) for the adjacency list and stack.

Why Hierholzer’s works here

An Eulerian path exists if:

• The graph is connected (considering only vertices with edges).
• At most one vertex has out_degree - in_degree = 1 (start).
• At most one vertex has in_degree - out_degree = 1 (end).
• All other vertices have equal in-degree and out-degree.

The problem guarantees a valid itinerary exists starting from JFK, so these conditions are met.

Why simple DFS fails

A simple DFS might get stuck at a dead end before using all edges. For example, with tickets JFK->A, JFK->B, B->JFK, a greedy DFS might go JFK->A and get stuck. Hierholzer’s backtracks correctly by appending to the route only after exhausting all edges from a node.

Transformation patterns summary

Pattern	Technique	Key data structure
Deep copy with cycles	DFS/BFS + hash map	Dict (original->clone)
Valid tree check	Edge count + BFS/UF	DSU or visited set
Find centroids	Topological leaf peeling	Degree array + queue
Eulerian path	Hierholzer’s	Adjacency list + stack

Big-O summary

Problem	Time	Space
Clone Graph	O(V + E)	O(V)
Graph Valid Tree	O(V + E)	O(V)
Minimum Height Trees	O(V)	O(V)
Reconstruct Itinerary	O(E log E)	O(E)

Common mistakes

1. Clone Graph — forgetting the hash map: Without mapping original nodes to clones, you either clone nodes multiple times or loop forever on cycles.

2. Valid Tree — only checking acyclicity: A forest (disconnected acyclic graph) is not a tree. You must check both connectivity and acyclicity.

3. MHT — not handling n <= 2: When n is 1, return [0]. When n is 2, return [0, 1]. The leaf-peeling loop does not handle these base cases correctly.

4. Itinerary — using DFS without Hierholzer’s: A simple DFS may get stuck at dead ends. Hierholzer’s backtracks correctly by appending to the route only after exhausting all edges from a node.

5. Itinerary — wrong sort order: Sorting destinations in ascending order and using pop(0) is O(n) per removal. Sort in descending order and use pop() for O(1) removal.

6. Valid Tree — undirected edge double-counting: When checking for cycles with DFS, skip the parent node to avoid counting the same undirected edge as a back edge.

Practice problems

Problem	Difficulty	Key Concept
Clone Graph - LeetCode 133	Medium	DFS/BFS with hash map cloning
Graph Valid Tree - LeetCode 261	Medium	Edge count + connectivity check
Minimum Height Trees - LeetCode 310	Medium	Topological leaf peeling
Reconstruct Itinerary - LeetCode 332	Hard	Hierholzer’s Eulerian path
Copy List with Random Pointer - LeetCode 138	Medium	Same clone pattern for lists
Number of Connected Components - LeetCode 323	Medium	Union-Find or BFS connectivity
Find the Town Judge - LeetCode 997	Easy	In-degree and out-degree analysis

Key takeaways

• Cloning a graph requires a hash map from original to clone nodes to handle cycles and shared references correctly.
• A valid tree has exactly n - 1 edges and is fully connected. Check both conditions — missing either leads to incorrect results.
• Tree centroids are found by repeatedly peeling leaves inward. At most 2 centroids exist, located at the middle of the diameter path.
• Hierholzer’s algorithm solves Eulerian path problems by greedily traversing edges and backtracking when stuck.
• Sort destinations in reverse order and use pop() for efficient lexicographic ordering in itinerary problems.