LT #261: Graph Valid Tree

Day: 7
Type: Graphs
Level: Medium
Link: https://leetcode.com/problems/graph-valid-tree/description/

What is a Valid Tree?

A valid tree has the following properties:

1. Connected: Every node in the graph must be reachable from every other node. In other words, the graph must have exactly one connected component.
2. Acyclic: The graph must not contain any cycles.

TL:DR

Algorithm: DFS
Approach: Create a HashMap with neighbors for each node (since it’s undirected — will keep track of both directions).
Visited set will keep track of node traversal.
Run DFS starting from Node 0 and keeping track of parent/prev node to ensure parent node being in visited doesn’t return False for the DFS. For new neighbors for each node, add them in visited and run DFS on them again.

Solving the problem

1. Creating the HashMap for neighbors

 neighbors = {i: [] for i in range(n)} # creates dictionary with each node having an empty list

 for node1, node2 in edges: # e.g. [0, 1]
            neighbors[node1].append(node2) # e.g capturing 0 -> 1
            neighbors[node2].append(node1) # capturing other direction 1 -> 0

2. Calling the DFS —

    # Perform DFS from node 0 - prev value is set to -1 to be unique
    if not dfs(0, -1):
        return False

    # Ensure all nodes were visited (i.e., the graph is connected) and dfs returned True
    return len(visited) == n 

3. Defining the DFS Algorithm

        def dfs(node, prev):
            visited.add(node)
            if (neighbors[node] == []): # this would be possible only if one of the nodes is disconnected
                return False
            for neighbor in neighbors[node]:
                if neighbor == prev: # skip this neighbor as this is parent and will be in visited
                    continue
                if neighbor in visited: # if neighbor already there in set then return False
                    return False
                else:
                    if not dfs(neighbor, node): # if True - do nothing else exit dfs with False
                        return False
            return True

Complete Python code —

        if len(edges) != n - 1:
            return False 
        if edges == []:
            return True

        neighbors = {i: [] for i in range(n)}
        visited = set()
        
        for node1, node2 in edges:
            neighbors[node1].append(node2)
            neighbors[node2].append(node1)
        
        def dfs(node, prev):
            visited.add(node)
            if (neighbors[node] == []):
                return False
            for neighbor in neighbors[node]:
                if neighbor == prev:
                    continue
                if neighbor in visited:
                    return False
                else:
                    if not dfs(neighbor, node):
                        return False
            return True
    
        # Perform DFS from node 0 - prev value is set to -1 to be unique
        if not dfs(0, -1):
          return False

        # Ensure all nodes were visited (i.e., the graph is connected) and dfs returned True
          return len(visited) == n

Example — n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]

neighbors = {0: [1], 1: [0, 2, 3, 4], 2: [1, 3], 3: [2, 1], 4: [1]}

DFS Stack visualization

Time Complexity:

• O(n + e), where n is the number of nodes and e is the number of edges. This is because DFS visits each node and edge exactly once.

Space Complexity:

• O(n) for storing the adjacency list and the visited set.