How to Solve: Graph Valid Tree

How to Solve: Graph Valid Tree

Complete Guide for FAANG-Level Interviews

? Introduction

"This single problem tests three core graph concepts—union-find, cycle detection, and connectivity—in one shot. Master it, and you’ll crush 90% of graph questions in FAANG interviews."

? WHAT YOU NEED TO KNOW FIRST

Before tackling Graph Valid Tree, ensure you understand: 1. Union-Find (Disjoint Set Union - DSU) – For efficient cycle detection and connectivity checks. 2. DFS/BFS Traversal – To explore graph connectivity and detect cycles. 3. Graph Representations – Adjacency lists vs. edge lists (when to use each).

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK

Mental checklist for every "Graph Valid Tree" problem:

1. Check Edge Count

2. If edges.length != n - 1, return False (a tree must have exactly n-1 edges).

3. Choose a Graph Representation

4. Adjacency List? → Use DFS/BFS for cycle detection.

5. Edge List? → Use Union-Find for efficiency.

6. Detect Cycles

7. Union-Find: For each edge (u, v), if find(u) == find(v), a cycle exists.

8. DFS/BFS: Track visited and parent to avoid false cycles.

9. Check Connectivity

10. Union-Find: After processing all edges, check if all nodes have the same root.

11. DFS/BFS: Run traversal from any node; if len(visited) != n, it’s disconnected.

12. Return Result

13. If no cycles and fully connected, return True. Else, False.

? WORKED EXAMPLES

Example 1 – Basic (Union-Find)

Problem: Given n nodes labeled 0 to n-1 and a list of edges, determine if the graph is a valid tree.

Input: n = 5, edges = [[0,1], [0,2], [0,3], [1,4]] Output: True

Solution (Union-Find)

class UnionFind:

    def __init__(self, size):

        self.parent = list(range(size))

        self.rank = [0]  size


    def find(self, x):

        if self.parent[x] != x:

            self.parent[x] = self.find(self.parent[x])  # Path compression

        return self.parent[x]


    def union(self, x, y):

        x_root = self.find(x)

        y_root = self.find(y)

        if x_root == y_root:

            return False  # Cycle detected

        # Union by rank

        if self.rank[x_root] < self.rank[y_root]:

            self.parent[x_root] = y_root

        else:

            self.parent[y_root] = x_root

            if self.rank[x_root] == self.rank[y_root]:

                self.rank[x_root] += 1

        return True

def validTree(n, edges):

    if len(edges) != n - 1:

        return False

    uf = UnionFind(n)

    for u, v in edges:

        if not uf.union(u, v):

            return False  # Cycle detected

    return True  # No cycles + fully connected

Time Complexity: O(n α(n)) (near-linear due to path compression) Space Complexity: O(n) (for parent and rank arrays)

Why this works: - Union-Find efficiently checks for cycles and connectivity in near-constant time per operation. - The edge count check (n-1 edges) is a quick early termination.

Example 2 – Medium (DFS Cycle Detection)

Problem: Same as above, but edges are given as an adjacency list.

Input: n = 5, edges = {0: [1,2,3], 1: [0,4], 2: [0], 3: [0], 4: [1]} Output: True

Solution (DFS)

def validTree(n, edges):

    if len(edges) != n - 1:

        return False

    graph = {i: [] for i in range(n)}

    for u, v in edges:

        graph[u].append(v)

        graph[v].append(u)


    visited = set()


    def dfs(node, parent):

        if node in visited:

            return False

        visited.add(node)

        for neighbor in graph[node]:

            if neighbor != parent and not dfs(neighbor, node):

                return False

        return True


    return dfs(0, -1) and len(visited) == n

Time Complexity: O(n + e) (DFS traversal) Space Complexity: O(n) (recursion stack + visited set)

Why this works: - DFS tracks parent to avoid false cycles (e.g., 0 → 1 → 0 is not a cycle if 1’s parent is 0). - The len(visited) == n check ensures connectivity.

Example 3 – Hard (Follow-Up: Disconnected Components)

Problem: Given n nodes and edges, determine if the graph is a forest of trees (i.e., no cycles and all components are trees).

Input: n = 5, edges = [[0,1], [2,3]] Output: True (two trees: 0-1 and 2-3)

Solution (Union-Find with Component Count)

def validForest(n, edges):

    if len(edges) > n - 1:  # More edges than a forest allows

        return False

    uf = UnionFind(n)

    components = n

    for u, v in edges:

        if uf.union(u, v):

            components -= 1

        else:

            return False  # Cycle detected

    return components == len(edges) + 1  # Forest has `components` trees

Time Complexity: O(n α(n)) Space Complexity: O(n)

Why this works: - A forest with k trees has n - k edges. Here, components = k, so edges = n - k. - Union-Find tracks the number of connected components.

❌ Common Mistakes

?️ INTERVIEW TrapS

? 1-Minute Recap

"Alright, let’s lock this in. To solve Graph Valid Tree: 1. First, check if the edge count is n-1. If not, it’s not a tree. 2. Pick your weapon:
- Union-Find for edge lists (fast, clean, optimal).
- DFS/BFS for adjacency lists (track parent to avoid false cycles). 3. Detect cycles:
- Union-Find: find(u) == find(v) → cycle.
- DFS: neighbor != parent → no cycle. 4. Check connectivity:
- Union-Find: All nodes share the same root.
- DFS/BFS: len(visited) == n. 5. Return True only if no cycles and fully connected.

Pro tip: If the interviewer asks about forests, remember: a forest is just multiple trees, so relax the connectivity check but still enforce n - k edges for k trees.

You’ve got this. Now go ace that interview!

? Final Notes

• Practice Variations: Try problems like "Number of Connected Components" or "Redundant Connection" to reinforce the pattern.
• Whiteboard Template: Sketch the Union-Find/DFS steps before coding.
• Edge Cases: Test with n = 1 (no edges), n = 2 (one edge), and disconnected graphs.

This framework is battle-tested—use it verbatim in your interview. Good luck! ?