Graph Valid Tree
Problem
Given n nodes and a list of undirected edges, return true if they form a valid tree: connected, with no cycle.
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
Test cases
Case 1
Input: 5, [[0,1],[0,2],[0,3],[1,4]] Expected: true
Case 2
Input: 5, [[0,1],[1,2],[2,3],[1,3],[1,4]] Expected: false
Case 3
Input: 4, [[0,1],[2,3]] Expected: false
View solutionHide solution1 approach
1. Edge count + Union-Find
Time O(n · α(n))Space O(n)
A tree on n nodes has exactly n − 1 edges and no cycle. With the right edge count, any union that finds both ends already joined means a cycle.
function validTree(n, edges) { if (edges.length !== n - 1) return false; const parent = [...Array(n).keys()]; const find = (x) => (parent[x] === x ? x : (parent[x] = find(parent[x]))); for (const [a, b] of edges) { const ra = find(a), rb = find(b); if (ra === rb) return false; parent[ra] = rb; } return true;}