Graph Valid Tree

Medium

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}