Graph Valid Tree — Medium Coding Interview Question

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

Example

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

Output: true

Constraints

• 1 <= n <= 2000

Topics & Companies

Topics: graphs

Asked by: Google, LinkedIn

Optimal Solution Complexity

Time complexity: O(V alpha(V)). Space complexity: O(V).

Practice more

• All DSA Problems
• DSA Patterns