#277 Valid Tree

medium

javascript

blind75

graph

union-find

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

A valid tree must:

Be connected (all nodes can be reached)
Have no cycles
Have exactly n-1 edges

Constraints:

1 ≤ n ≤ 100
0 ≤ edges.length ≤ n * (n-1) / 2
No duplicate edges
Edges are undirected ([0,1] is same as [1,0])

Examples:

// Example 1:

const n1 = 5;
const edges1 = [[0,1], [0,2], [0,3], [1,4]];
console.log(validTree(n1, edges1));
// Output: true

// Explanation: Forms a valid tree with 4 edges and 5 nodes


// Example 2:

const n2 = 5;
const edges2 = [[0,1], [1,2], [2,3], [1,3], [1,4]];
console.log(validTree(n2, edges2));
// Output: false

// Explanation: Contains a cycle between nodes 1-2-3