# C++ iterative solution

• Build graph by input, use bfs to check every node's neighbor.
If the neighbor is not parent and is visited, then there is a cycle, return false.
Else put this neighbor in the queue.

``````class Solution {
public:
struct node{
int parent=0;
vector<int>neighbors;
};
bool validTree(int n, vector<pair<int, int>>& edges) {
unordered_map<int,node>nodes;
if(edges.size()!=n-1)return false;
vector<bool>v(n,false);
for(auto edge:edges){
nodes[edge.first].neighbors.push_back(edge.second);
nodes[edge.second].neighbors.push_back(edge.first);
}
queue<int>q;
q.push(0);
v[0]=true;
while(!q.empty()){
int p=q.front();
q.pop();
for(auto n:nodes[p].neighbors){
if(n!=nodes[p].parent){
if(v[n])return false;
v[n]=true;
nodes[n].parent=p;
q.push(n);
}
}
}
return true;
}
};``````

• A great solution! But I think it is BFS instead of DFS. Note that you keep all the nodes in the same level in a `queue`.

• Yea, you are right, I am wrong. It is BFS. Thanks for the correction.

• Your code gives a wrong answer in a few cases. You have not checked connected properly. You need the following

for (int i=0; i<n; i++)
if (!v[i]) return false;

• And since the nodes are from [0,n), I can just use vector<int> and do not need a struct node. The following is accepted version.

``````class Solution {
public:

bool validTree(int n, vector<pair<int, int>>& edges) {
if(edges.size()!=n-1) return false;
vector<vector<int>> neighbors (n, vector<int> ());
for (int i=0; i<edges.size(); i++) {
neighbors[edges[i].first].push_back(edges[i].second);
neighbors[edges[i].second].push_back(edges[i].first);
}
vector<int> childparent (n,0);
vector<int> visited  (n, false);
queue<int> Q;
Q.push(0);visited[0]=true;

while (!Q.empty()) {
int p = Q.front();
Q.pop();
for (int i=0; i<neighbors[p].size(); i++) {
if (childparent[p]!= neighbors[p][i]) {
if ( visited[neighbors[p][i]]) return false;
Q.push(neighbors[p][i]);
visited[neighbors[p][i]] = true;
childparent[neighbors[p][i]] = p;
}
}
}
for (int i=0; i<n; i++)
if (!visited[i]) return false;
return true;

}
};``````

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