Graph Valid Tree
Determine if a set of edges forms a valid tree.
Examples
No cycles, fully connected.
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
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.
Dry Run
Input: n = 5, edges = [[0,1], [1,2], [2,3], [1,3], [1,4]]
Adjacency list: 0:[1], 1:[0,2,3,4], 2:[1,3], 3:[2,1], 4:[1]
| Step | Call | Visited | Action |
|---|---|---|---|
| 1 | dfs(0, -1) |
{0} | Mark 0. Neighbour 1: call dfs(1, 0). |
| 2 | dfs(1, 0) |
{0, 1} | Mark 1. Neighbour 0 is the parent: skip. Neighbour 2: call dfs(2, 1). |
| 3 | dfs(2, 1) |
{0, 1, 2} | Mark 2. Neighbour 1 is the parent: skip. Neighbour 3: call dfs(3, 2). |
| 4 | dfs(3, 2) |
{0, 1, 2, 3} | Mark 3. Neighbour 2 is the parent: skip. Neighbour 1: call dfs(1, 3). |
| 5 | dfs(1, 3) |
{0, 1, 2, 3} | 1 is already visited. The edge 3-1 closes the cycle 1-2-3. Return false. |
| 6 | Unwind | — | dfs(3, 2), dfs(2, 1), dfs(1, 0) and dfs(0, -1) each return false. The answer is false. |
Edge Cases & Common Mistakes
- Disconnected Graph: No cycle, but not a tree (forest). Must check
visited.size() == n. - Single Node: LeetCode guarantees
n ≥ 1. One node with no edges is a valid tree: there is no cycle, and DFS from node 0 reaches everything. - Self-Loops and Repeated Edges: LeetCode rules both out, and the parent check relies on it: a second copy of the edge back to the parent would be skipped too, so that two-edge cycle would go unnoticed.
Solution
DFS from node 0 with the parent passed down, then a check that every node was visited. Reaching a visited node through any edge except the one back to the parent means a cycle.
Note: LeetCode 261 is a Premium problem.
Graph Valid Tree Code
1var validTree = function(n, edges) {2 const graph = Array.from({ length: n }, () => []);3 for (const [a, b] of edges) {4 graph[a].push(b);5 graph[b].push(a);6 }78 const visited = new Array(n).fill(false);910 function dfs(node, parent) {11 if (visited[node]) {12 return false;13 }14 visited[node] = true;15 for (const neighbor of graph[node]) {16 if (neighbor === parent) {17 continue;18 }19 if (!dfs(neighbor, node)) {20 return false;21 }22 }23 return true;24 }2526 if (!dfs(0, -1)) {27 return false;28 }29 for (let node = 0; node < n; node++) {30 if (!visited[node]) {31 return false;32 }33 }34 return true;35};