Depth-First Search
Medium
Graph Valid Tree
Determine if a set of edges forms a valid tree.
10 min read
Solve on LeetCodeExamples
Input:n = 5, edges = [[0,1], [0,2], [0,3], [1,4]]
Output:true
Explain:
No cycles, fully connected.
Input:n = 5, edges = [[0,1], [1,2], [2,3], [1,3], [1,4]]
Output:false
Explain:
Cycle exists: 1-2-3-1.
Problem Understanding
A Tree is a special type of Graph that satisfies two conditions:
- Fully Connected: You can reach any node from any other node.
- Acyclic: It contains no cycles.
Alternatively: A graph with N nodes is a tree if it is fully connected and has exactly N - 1 edges.
Algorithm Strategy (DFS)
We can use DFS to check for cycles and connectivity.
- Build Graph: Create adjacency list.
- DFS from Node 0: Keep track of
visitedset to detect cycles.- Since the graph is undirected,
A-BmeansBis a neighbor ofA. We must not count the immediateparentas a cycle. - Pass
parentto the DFS call:dfs(node, parent). - If
neighbor != parentandneighboris visited -> Cycle Detected! Return false.
- Since the graph is undirected,
- Check Connectivity: After DFS,
visited.size()must equaln. If not, the graph is disconnected.
Visualization
Step 1 / 8
Problem: Is this a Valid Tree? (Connected, No Cycles). Start DFS(0).
1x
See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.Stop Guessing, Start Mastering.
Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.