Problem statement

https://leetcode.com/problems/graph-valid-tree/

Solution

We need to check two conditions: graph is connected and that number of nodes is one bigger than number of edges. So just traverse graph with dfs (or bfs) and check that all nodes are visited ant that len(edges) == n - 1.

Complexity

Time complexity is O(n + E), where n is number of nodes and E is number of edges. In fact we can iterrupt faster if number of edges is more than n, so we can make it O(n). Space complexity is O(n).

Code

class Solution:
    def validTree(self, n, edges):
        def dfs(node):
            visited[node] = 1
            for neib in graph[node]:
                if visited[neib] == 0: dfs(neib)
        
        visited = [0]*n
        graph = defaultdict(list)
        for a, b in edges:
            graph[a].append(b)
            graph[b].append(a)
        
        dfs(0)          
        return sum(visited) == n and len(edges) == n - 1