Neetcode - Graph Valid Tree
Simplicity is the ultimate sophistication.
Graph Valid Tree
Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.
Input:
n = 5
edges = [[0, 1], [0, 2], [0, 3], [1, 4]]
Output:
true
Input:
n = 5
edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]
Output:
false
Note:
- You can assume that no duplicate edges will appear in edges. Since all edges are
undirected,[0, 1]is the same as[1, 0]and thus will not appear together in edges.
This problem has several cases for deciding to proceed further or not. Here is the code I have written to solve this question.
class Solution {
private:
bool dfs(
int node, int parent,
const map<int, vector<int>>& m,
set<int>& visited){
visited.insert(node);
for (int ngb : m.at(node)) {
if (ngb == parent) continue;
if (visited.count(ngb) > 0) return false;
if(!dfs(ngb, node, m, visited)) return false;
}
return true;
}
public:
bool validTree(int n, vector<vector<int>>& edges) {
if (edges.size() != n - 1) return false;
if (n == 1 && edges.empty()) return true;
map<int, vector<int>> m;
for (const auto &edge : edges) {
int f = edge[0], s = edge[1];
m[f].push_back(s);
m[s].push_back(f);
}
if (m.size() != n) return false;
set<int> visited;
if (!dfs(0, -1, m, visited)) return false;
return visited.size() == n;
}
};DFS - CSY
The function first checks if the number of edges is exactly n-1, a requirement for a tree with n nodes, using if (edges.size() != n - 1) return false;. This ensures the graph has the correct edge count but doesn’t guarantee connectivity or acyclicity. Next, I construct an adjacency list using a map, where each node maps to a vector of its neighbors, by adding both directions of each edge (f -> s and s -> f) to represent an undirected graph. I handle edge cases: if n=1 and there are no edges, it’s a valid tree, so return true; if fewer than n nodes appear in the adjacency list (m.size() < n), there are isolated nodes, so return false.
The core logic is a recursive DFS function, which takes four arguments: the current node, its parent node, the adjacency list (passed by const reference), and a set to track visited nodes. In DFS, I mark the current node as visited, then iterate over its neighbors.
If a neighbor is the parent, I skip it to avoid false cycle detection in undirected graphs. If a neighbor is already visited (and not the parent), a cycle exists, so I return false. Otherwise, I recursively call DFS on unvisited neighbors, passing the current node as the parent. DFS is called once from node 0, and if it returns false, a cycle was found, so the function returns false. Finally, I check if visited.size() == n to ensure all nodes are connected in one component. If both conditions (no cycles and full connectivity) are met, the function returns true. That's it.
