Bug Report for valid-tree

[alinvm]

Bug Report for https://neetcode.io/problems/valid-tree

Please describe the bug below and include any steps to reproduce the bug or screenshots if possible.

Wrong solution is accepted (the dfs return value is not propagated up the call stack)

private static boolean dfs(List<List<Integer>> graph, Set<Integer> visited, int node, int parent) {
    visited.add(node);
    for (var nei : graph.get(node)) {
      if (nei == parent) continue;
      if (!visited.contains(nei)) {
        dfs(graph, visited, nei, node); // <---------- the dfs return value is not propagated up the call stack
      } else {
        return true;
      }
    }
    
    return false;
  }

Manually running the following test case which contains a cycle also passes because expected is false

n=6 edges=[[0,1],[1,2],[2,3],[3,4],[4,1],[1,5]]

[Srihari2222]

Could you share the complete code?

[alinvm]

class Solution {
    public boolean validTree(int n, int[][] edges) {
        List<List<Integer>> graph = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        
        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }

        var visited = new HashSet<Integer>();
        var hasCycle = dfs(graph, visited, 0, -1);
        var isConnected = visited.size() == n;

        return !hasCycle && isConnected; 
    }

  private static boolean dfs(List<List<Integer>> graph, 
                              Set<Integer> visited, 
                              int node,
                              int parent) {
    visited.add(node);
    for (var nei : graph.get(node)) {
      if (nei == parent) continue;
      if (!visited.contains(nei)) {
        dfs(graph, visited, nei, node);
      } else {
        return true;
      }
    }
    
    return false;       
  }
}