MediumBlind75GraphDFSBFSUnion Find

Graph Valid Tree

Given n nodes labeled from 0 to n-1 and a list of undirected edges, check if these edges form a valid tree.

Examples

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

All nodes are connected with no cycles.

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

There is a cycle: 1->2->3->1.

Constraints

  • •1 <= n <= 2000
  • •0 <= edges.length <= 5000
  • •edges[i].length == 2
  • •0 <= ai, bi < n
  • •ai != bi
  • •There are no self-loops or repeated edges.

Approaches

Check for cycles and connectivity using DFS.

CodeT: O(V + E) | S: O(V + E)
def valid_tree(n, edges):
    if len(edges) != n - 1:
        return False
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    visited = [False] * n
    def dfs(node, parent):
        visited[node] = True
        for neighbor in graph[node]:
            if not visited[neighbor]:
                if not dfs(neighbor, node):
                    return False
            elif neighbor != parent:
                return False
        return True
    if not dfs(0, -1):
        return False
    return all(visited)

Use BFS to check connectivity and edge count for cycle detection.

CodeT: O(V + E) | S: O(V + E)
from collections import deque

def valid_tree(n, edges):
    if len(edges) != n - 1:
        return False
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    visited = [False] * n
    queue = deque([0])
    visited[0] = True
    count = 1
    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if not visited[neighbor]:
                visited[neighbor] = True
                count += 1
                queue.append(neighbor)
    return count == n

Use Union Find to detect cycles and check connectivity.

Diagram

n=5, edges=[[0,1],[0,2],[0,3],[1,4]] Union: (0,1), (0,2), (0,3), (1,4) All unions succeed (no cycles) Edges = 4 = n-1 = 4 -> True
CodeT: O(n * alpha(n)) | S: O(n)
def valid_tree(n, edges):
    parent = list(range(n))
    rank = [0] * n
    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]
    def union(x, y):
        px, py = find(x), find(y)
        if px == py:
            return False
        if rank[px] < rank[py]:
            px, py = py, px
        parent[py] = px
        if rank[px] == rank[py]:
            rank[px] += 1
        return True
    for u, v in edges:
        if not union(u, v):
            return False
    return len(edges) == n - 1

Complexity Comparison

DFS - Cycle Detection + Connectivity
T: O(V + E)S: O(V + E)

Check for cycles and connectivity using DFS.

BFS - Connectivity Check
T: O(V + E)S: O(V + E)

Use BFS to check connectivity and edge count for cycle detection.

Union Find
T: O(n * alpha(n))S: O(n)

Use Union Find to detect cycles and check connectivity.

Common Mistakes

Not checking both conditions (n-1 edges AND connectivity)

Using Union Find without path compression (less efficient)

Forgetting that a tree must have exactly n-1 edges

Try It Yourself

Copy the optimal solution and run it in our compiler.

▶Open in Compiler
← All Problems