Graph Valid Tree
MediumConnected, and exactly V-1 edges
Problem
Given n nodes and edges, return whether they form a valid tree (connected and acyclic).
A valid tree has exactly n-1 edges, is fully connected, and contains no cycle.
The idea
A tree is a connected acyclic graph, and with exactly V-1 edges connectivity alone implies acyclicity. So check the edge count first, then confirm one traversal reaches every node.
The trick
- edges != V-1 is an immediate no.
- Then one DFS or BFS must visit all V nodes.
- Union-find works too: a union that finds both ends already joined is a cycle.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — n=5, edges=[[0,1],[0,2],[0,3],[1,4]] Values: 0, 1.
1if edges != n-1: false2DFS/union-find from node 0; valid if all nodes reached and no cycleInput
- array
- [0, 1]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- n=5, edges=[[0,1],[0,2],[0,3],[1,4]]
- Output:
- true
- Explanation:
- Connected with no cycle → a tree.
Example 2
- Input:
- n=5, edges=[[0,1],[1,2],[2,3],[1,3],[1,4]]
- Output:
- false
- Explanation:
- Has a cycle → not a tree.
Example 3
- Input:
- n=2, edges=[[0,1]]
- Output:
- true
- Explanation:
- Two nodes, one edge.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.