261.Graph_Valid_Tree(Medium).md

261. Graph Valid Tree (Medium)

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

Date	Stopwatch	Y/N	Feedback
Jul 6, 2025	20m 52s	Y	First time
Jul 8, 2025	8m 36s	Y	Improvement on code

Edge Cases:

Edge Case 1:

Input: n = 4, edges = [[0,1],[2,3]]
Output: false
Explanation: Two connected components, not a tree

Walk-through:

1. Build graph

2. Run DFS with (node, prev), if node in visited we should return False. Otherwise, add this new node into visited(). Then, we explore other nodes of node, we only explore the node if nei != prev, we don't want to explore the previous node. Otherwise, we run DFS to check (nei, node).

3. Pay attention to edge case, even though the constraint mentions there is no self-loop, but we can have multiple connected components within the tree, so it can only be checked by comparing total nodes and nodes in visited().

Python:

class Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        # Q: Check if this is a valid tree
        # S: 1. Build graph
        # 2. Run DFS from 0 with prev to keep track of previous node, if a node has neighbor in visited(), return False
        # 3. Check the total nodes we've visited == n
        # TC: O(V+E), SC: O(V+E)

        graph = defaultdict(list)
        visited = set()
        # Build graph
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)
        # Run DFS
        def dfs(node, prev):
            if node in visited:
                return False
            visited.add(node)
            # Explore node's neighbors
            for nei in graph[node]:
                if nei != prev:
                    if not dfs(nei, node):
                        return False
            return True
        return dfs(0, -1) and len(visited) == n

Time Complexity: $O(V+E)$
Space Complexity: $O(V+E)$