LeetEye LeetEye
Medium Graph Traversal ~5 min

Graph Valid Tree

graphs graph-valid-tree

Problem

You have a graph of n nodes labeled from 0 to n - 1. You are given an integer n and a list of edges where edges[i] = [ai, bi] indicates that there is an undirected edge between nodes ai and bi in the graph.

Return true if the edges of the given graph make up a valid tree, or false otherwise.

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 (has cycle: 1-2-3-1)
Key Insight

A tree has exactly n-1 edges, is connected, and has no cycles.

Valid tree: exactly n-1 edges AND connected. Check edge count first, then verify all nodes reachable via DFS/BFS.

How to Approach This Problem

Pattern Recognition: When you see keywords like graph valid tree graphs, think Graph Traversal.

Step-by-Step Reasoning

1 A tree with n nodes has exactly:
Answer: n - 1 edges
Tree is minimally connected. n-1 edges for n nodes.
2 If len(edges) != n - 1:
Answer: It's definitely not a tree
Too few edges = disconnected. Too many = cycle.
3 If len(edges) == n - 1:
Answer: It's a tree iff connected
n-1 edges and connected → no cycles (exactly enough edges). n-1 edges and disconnected → some component has extra edges (cycle).
4 To check if all nodes are connected:
Answer: DFS/BFS from any node, count visited
If DFS visits all n nodes, graph is connected.
5 Using Union-Find to check valid tree:
Answer: All of above
Union-Find detects cycles (union nodes already connected) and counts components.

Solution

def validTree(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 = {i: [] for i in range(n)}
    for a, b in edges:
        graph[a].append(b)
        graph[b].append(a)
    
    # Check if all nodes are connected (DFS from node 0)
    visited = set()
    
    def dfs(node):
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                dfs(neighbor)
    
    dfs(0)
    
    return len(visited) == n

Complexity Analysis

Time O(n)
Space O(n)

Master This Pattern

Build intuition with interactive MCQs. Practice Graph Traversal problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye