Graph Valid Tree - codepath/compsci_guides GitHub Wiki

Unit 12 Session 2 Advanced (Click for link to problem statements)

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 20-30 mins
  • 🛠️ Topics: Graphs, DFS, Cycle Detection, Connectivity

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Established a set (2-3) of test cases to verify their own solution later.
  • Established a set (1-2) of edge cases to verify their solution handles complexities.
  • Have fully understood the problem and have no clarifying questions.
  • Have you verified any Time/Space Constraints for this problem?

  • What is a valid tree?

    • A valid tree is an acyclic connected graph that contains exactly n-1 edges for n nodes.

  • What if the graph contains fewer than n-1 edges?

    • It cannot be a valid tree, as it would be disconnected.

  • Can the graph have no nodes or no edges?

    • Yes, a graph with n=1 node and no edges is a valid tree.
HAPPY CASE
Input: n = 5, edges = [0,1],[0,2],[0,3],[1,4](/codepath/compsci_guides/wiki/0,1],[0,2],[0,3],[1,4)
Output: True
Explanation: All nodes are connected, and there are no cycles.

Input: n = 5, edges = [0,1],[1,2],[2,3],[1,3],[1,4](/codepath/compsci_guides/wiki/0,1],[1,2],[2,3],[1,3],[1,4)
Output: False
Explanation: A cycle is present, so it is not a valid tree.

EDGE CASE
Input: n = 1, edges = []
Output: True
Explanation: A single node without any edges is a valid tree.

Input: n = 2, edges = [0,1],[1,0](/codepath/compsci_guides/wiki/0,1],[1,0)
Output: True
Explanation: The two nodes are connected, forming a valid tree.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Graph Traversal and Tree Validation, consider the following approaches:

  • DFS/BFS for Connectivity Check: Traverse the graph to ensure all nodes are reachable.
  • Cycle Detection: Use DFS to detect cycles.
  • Edge Count Check: For a valid tree, the graph must have exactly n-1 edges.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:
To validate a tree, we need to:

  1. Ensure the graph has exactly n-1 edges (necessary for connectivity).
  2. Use DFS to ensure the graph is connected and has no cycles.
  3. Check if all nodes were visited during the DFS traversal (graph is connected).
1) If the number of edges is not `n-1`, return False.
2) Build the adjacency list representation of the graph.
3) Use DFS to check if the graph is connected and has no cycles.
4) If all nodes are visited, return True. Otherwise, return False.

⚠️ Common Mistakes

  • Forgetting to handle cases where the graph has fewer than n-1 edges.
  • Not checking for cycles correctly (e.g., backtracking through the parent node).

4: I-mplement

Implement the code to solve the algorithm.

def valid_tree(n, edges):
    # A valid tree must have exactly n - 1 edges
    if len(edges) != n - 1:
        return False
    
    # Build the adjacency list representation of the graph
    adj_list = {i: [] for i in range(n)}
    for a, b in edges:
        adj_list[a].append(b)
        adj_list[b].append(a)
    
    # Set to keep track of visited nodes
    visited = set()
    
    # DFS function to check if the graph is connected and acyclic
    def dfs(node, parent):
        visited.add(node)
        for neighbor in adj_list[node]:
            if neighbor == parent:
                continue  # Skip the parent to avoid false cycle detection
            if neighbor in visited:
                return False  # Cycle detected
            if not dfs(neighbor, node):
                return False
        return True
    
    # Start DFS from node 0
    if not dfs(0, -1):
        return False
    
    # Check if all nodes were visited (graph is connected)
    return len(visited) == n

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

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

    • DFS traversal: Visits all nodes, no cycles detected.
    • Output: True

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

    • DFS traversal: Detects a cycle between nodes 1 and 3.
    • Output: False

  • Input: n = 1, edges = []

    • Output: True (A single node is a valid tree.)

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N is the number of nodes and E is the number of edges.

  • Time Complexity: O(N + E) since we traverse the graph during DFS.
  • Space Complexity: O(N) for storing the adjacency list and visited set.