Graph Valid Tree
Medium · Graphs
You are given an integer n representing nodes labeled 0 to n-1, and a list of undirected edges connecting pairs of these nodes. Determine whether these edges form a valid tree, meaning the graph is fully connected and contains no cycles. Return true if it is a valid tree, false otherwise.
Examples
Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
Output: true
Why: All 5 nodes are connected using exactly 4 edges with no cycle, so it is a valid tree.Input: n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]
Output: false
Why: Nodes 1, 2 and 3 form a cycle, so the graph cannot be a tree.Input: n = 4, edges = [[0,1],[2,3]]
Output: false
Why: There are two separate components, so the graph is not fully connected and thus not a tree.Constraints
1 <= n <= 2000, 0 <= edges.length <= 5000, edges[i].length == 2, 0 <= edges[i][0], edges[i][1] < n, no self-loops or duplicate edges
Practise it by voice
Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.
This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Graph Valid Tree. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.