Solutions

# A graph is a tree if it's fully connected and has no cycles. A tree with n nodes has exactly n - 1 edges. DFS or BFS checking if the node is already visited to detect cycle, and also check if all nodes are visited at the end.
# graphs

# DFS - O(E + V) time, O(E + V) space
def validTree(n: int, edges: list[list[int]]) -> bool:
    if len(edges) > n - 1:
        return False

    adjmap = {i: [] for i in range(n)}
    for u, v in edges:
        # NB: a tree is an undirected graph, so add both ways!
        adjmap[u].append(v)
        adjmap[v].append(u)

    visited = set()

    def dfs(node: int, parent: int) -> bool:
        if node in visited:
            return False

        visited.add(node)
        for adj in adjmap[node]:
            if adj == parent: # don't go back to parent
                continue
            if not dfs(adj, node):
                return False
        return True

    return dfs(0, -1) and len(visited) == n

# BFS - O(E + V) time, O(E + V) space
def validTree(n: int, edges: list[list[int]]) -> bool:
    from collections import deque
    if len(edges) > n - 1:
        return False

    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)

    visit = set()
    q = deque([(0, -1)])  # (current node, parent node)
    visit.add(0)

    while q:
        node, parent = q.popleft()
        for nei in adj[node]:
            if nei == parent:
                continue
            if nei in visit:
                return False
            visit.add(nei)
            q.append((nei, node))

    return len(visit) == n