LeetCode #261: Graph Valid Tree

LeetCode Solutions

https://leetcode.com/problems/graph-valid-tree/

The problem asks us to determine if the given set of edges forms a valid tree. A tree is defined as a connected, acyclic graph, which means there should be no cycles in the graph and all nodes should be connected.

To solve this problem, we can use depth-first search (DFS) to traverse the graph and check for cycles. We start at any node and keep track of the nodes we have visited. If we visit a node that has already been visited, then we have a cycle and the graph is not a valid tree.

We also need to make sure that all nodes are connected. If there are disconnected nodes, then the graph cannot be a tree.

Here are the steps to solve the problem:

  1. Create an adjacency list from the given edges. We can use a dictionary to store the adjacency list.
  2. Start a DFS from any node, keeping track of visited nodes.
  3. If we visit a node that has already been visited, then we have a cycle and the graph is not a valid tree. Return False.
  4. If all nodes are visited and we haven’t found a cycle, check if the number of visited nodes is equal to the total number of nodes. If not, then the graph is not a valid tree. Return False.
  5. If we have visited all nodes and haven’t found a cycle, and the number of visited nodes is equal to the total number of nodes, then the graph is a valid tree. Return True.

Here’s the Python code that implements this algorithm:

class Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        if not n:
            return True
        adj = {i: [] for i in range(n)}
        for n1, n2 in edges:
            adj[n1].append(n2)
            adj[n2].append(n1)

        visit = set()
        def dfs(i, prev):
            if i in visit:
                return False
            visit.add(i)
            for j in adj[i]:
                if j == prev:
                    continue
                if not dfs(j, i):
                    return False
            return True
        return dfs(0, -1) and n == len(visit)

Time and Space Complexity

The time complexity of this solution is O(V + E) where V is the number of vertices and E is the number of edges. The space complexity is O(V + E) to store the adjacency list and visited set.