FAANGPrep Sprint

Graph Valid Tree

Determine if a set of edges forms a valid tree.

MediumSolve on LeetCode

Examples

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 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.

Visualization

GREEN = EDGES DFS WALKED · RED = THE EDGE THAT CLOSES A CYCLE

BUILD LIST

Edges

4 (n − 1 = 4)

Visited

0 / 5

Valid tree

—

call stack

No dfs running

Build the adjacency list: 5 lists, each of the 4 edges added to both ends

Call dfs(0, -1): start at node 0, which has no parent

edges

DFS from node 0 carries the node it came from. The edge back to that parent is skipped; any other edge that leads to a node already visited closes a cycle, and it turns red. Green edges are the ones DFS walked down. If DFS finishes without a cycle, the last check looks for a node it never reached — try the Two pieces preset.