Given n as the number of nodes and an array of the edges of a graph, find out if the graph is a valid tree. The nodes of the graph are labeled from 0 to n−1, and edges[i]=[x,y] represents an undirected edge connecting the nodes x and y of the graph. A graph is a valid tree when all the nodes are connected and there is no cycle between them.

graph-valid-tree.js

function validTree(n, edges) {
  // nodes from 0 to n-1
  // edges[i] = [x,y] edge between node x and node y
  // determine if graph is a valid tree (no cycles, no detached nodes)

  // this condition catches all cases when there are cycles (additional edges)
  if (edges.length !== n - 1) {
    return false;
  }

  const adjList = Array.from({ length: n }, () => []);
  edges.forEach(([x, y]) => {
    adjList[x].push(y);
    adjList[y].push(x);
  });

  const stack = [0];
  const visited = new Set();
  visited.add(0);

  // run dfs, add non-visited neighbors of the node to the stack
  while (stack.length > 0) {
    const node = stack.pop();
    const neighbors = adjList[node];
    neighbors.forEach((node) => {
      if (!visited[node]) {
        stack.push(node);
        visited[node] = true;
      }
    });
  }

  // if all nodes are visited, the condition is met
  return Object.keys(visited).length === n;
}

export { validTree };

// tc: while loop runs V times where V is the number of nodes
// inside while loop we have a forEach loop that runs E times in total (edges)
// O(E + V)
// sc: we have an adj list so O(E + V)