Graph Valid Tree — Cycle + Connected Check

Problem

Given n nodes (0 to n-1) and a list of undirected edges, determine if they form a valid tree.

Tree conditions: (1) No cycles, (2) All nodes connected → exactly n-1 edges and connected.

Solutions

Python — Union-Find

class Solution:
    def validTree(self, n: int, edges: list[list[int]]) -> bool:
        if len(edges)!=n-1: return False
        parent=list(range(n))
        def find(x):
            while parent[x]!=x: parent[x]=parent[parent[x]]; x=parent[x]
            return x
        for u,v in edges:
            pu,pv=find(u),find(v)
            if pu==pv: return False
            parent[pu]=pv
        return True

Python — DFS

from collections import defaultdict
class Solution:
    def validTree(self, n: int, edges: list[list[int]]) -> bool:
        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, parent):
            visited.add(node)
            for nb in adj[node]:
                if nb==parent: continue
                if nb in visited: return False
                if not dfs(nb,node): return False
            return True
        return dfs(0,-1) and len(visited)==n

Complexity

Time: O(V+E) | Space: O(V)