Graph Valid Tree

10 min read

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.

A Tree is a special type of Graph that satisfies two conditions:

Alternatively: A graph with N nodes is a tree if it is fully connected and has exactly N - 1 edges.

We can use DFS to check for cycles and connectivity.

Build Graph: Create adjacency list.
DFS from Node 0: Keep track of visited set to detect cycles.
- Since the graph is undirected, A-B means B is a neighbor of A. We must not count the immediate parent as a cycle.
- Pass parent to the DFS call: dfs(node, parent).
- If neighbor != parent and neighbor is visited -> Cycle Detected! Return false.
Check Connectivity: After DFS, visited.size() must equal n. If not, the graph is disconnected.

Step 1 / 1

Visualization coming soon...

Initializing...

Custom Input

Detecting a cycle by finding a 'back edge' to an already visited node.

Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.