# C# Solution - DFS

• Need to check

1. the connection between nodes
2. whether there is a cycle
``````public class Solution {
public bool ValidTree(int n, int[,] edges) {
int nodeCount = ValidateTree(0, -1, BuildGraph(n, edges), new bool[n], 0);

if (nodeCount == -1 || nodeCount != n)
return false;

return true;
}

private List<int>[] BuildGraph(int nodesVol, int[,] edges)
{
List<int>[] graph = new List<int>[nodesVol];

for (int i = 0; i <= edges.GetLength(0) - 1; i++)
{
if (graph[edges[i, 0]] == null)
graph[edges[i, 0]] = new List<int>();

if (graph[edges[i, 1]] == null)
graph[edges[i, 1]] = new List<int>();

}

return graph;
}

private int ValidateTree(int node, int preNode, List<int>[] graph, bool[] visited, int nodeCount)
{
visited[node] = true;
nodeCount++;

if (graph[node] != null)
{
foreach (var neighbor in graph[node])
if (!visited[neighbor])
nodeCount += ValidateTree(neighbor, node, graph, visited, 0);
else if (visited[neighbor] && neighbor != preNode)
return -1;
}

return nodeCount;
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.