Skip to main content

🟨 Graph Valid Tree (#261) 🔒

🔗 Problem Link​

📋 Problem Statement​

Given n nodes labeled from 0 to n - 1 and a list of undirected edges, write a function to check whether these edges make up a valid tree.

Note: This is a premium LeetCode problem, but available for free on NeetCode.

💡 Examples​

Example 1​

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

Example 2​

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

🔑 Key Insights & Approach​

Core Observation: A valid tree must have exactly n-1 edges and no cycles (be fully connected).

Why DFS/Union-Find?

  • Check edge count: must be n-1
  • Detect cycle using DFS or Union-Find
  • Verify all nodes connected
  • O(n + e) time

Approaches:

  1. DFS with cycle detection: O(n + e) time, O(n) space
  2. Union-Find: O(n + e) time, O(n) space
  3. BFS: O(n + e) time, O(n) space

Pattern: "Tree Validation" using graph properties.

🐍 Solution: Python​

Approach 1: DFS​

Time Complexity: O(n + e) | Space Complexity: O(n)

from typing import List
from collections import defaultdict

class Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        # Tree must have exactly n-1 edges
        if len(edges) != n - 1:
            return False

        # Build adjacency list
        graph = defaultdict(list)
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        visited = set()

        def dfs(node):
            visited.add(node)
            for neighbor in graph[node]:
                if neighbor not in visited:
                    dfs(neighbor)

        # Check if all nodes are connected
        dfs(0)
        return len(visited) == n

Approach 2: Union-Find​

Time Complexity: O(n * α(n)) | Space Complexity: O(n)

from typing import List

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):
            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
            parent[px] = py
            return True

        for u, v in edges:
            if not union(u, v):
                return False

        return True

🔵 Solution: Golang​

Approach: DFS​

Time Complexity: O(n + e) | Space Complexity: O(n)

func validTree(n int, edges [][]int) bool {
    if len(edges) != n-1 {
        return false
    }

    graph := make(map[int][]int)
    for _, edge := range edges {
        u, v := edge[0], edge[1]
        graph[u] = append(graph[u], v)
        graph[v] = append(graph[v], u)
    }

    visited := make(map[int]bool)

    var dfs func(node int)
    dfs = func(node int) {
        visited[node] = true
        for _, neighbor := range graph[node] {
            if !visited[neighbor] {
                dfs(neighbor)
            }
        }
    }

    dfs(0)
    return len(visited) == n
}

📚 References​