Graph Valid Tree - Video Solutions

Problem Overview: You are given n nodes labeled from 0 to n-1 and a list of undirected edges. The task is to determine whether these edges form a valid tree. A graph is a tree only if it is fully connected and contains no cycles. That means every node must be reachable from any other node, and the total number of edges must be exactly n - 1.

Approach 1: Union-Find (Disjoint Set) (O(n) time, O(n) space)

This approach uses the Union Find data structure to track connected components while processing edges. Start with each node in its own set. For every edge (u, v), check whether both nodes already belong to the same set using find(). If they do, adding the edge would create a cycle, so the graph cannot be a valid tree. Otherwise, merge the two sets using union(). A quick pre-check helps: a valid tree must have exactly n - 1 edges. If the edge count differs, return false immediately. Union-Find is efficient because path compression and union-by-rank keep operations nearly constant time. The overall complexity is O(n) time and O(n) space.

Approach 2: Depth-First Search (DFS) Traversal (O(n) time, O(n) space)

This method treats the problem as a graph traversal using Depth-First Search. First build an adjacency list from the edge list so you can quickly access neighbors of each node. Start DFS from node 0 and keep track of visited nodes. While exploring neighbors, ignore the node you came from (the parent) to avoid falsely detecting a cycle in an undirected graph. If DFS reaches a node that was already visited through another path, a cycle exists and the graph is not a valid tree. After traversal finishes, verify that all nodes were visited. If some nodes remain unvisited, the graph is disconnected. DFS visits each node and edge once, giving O(n) time and O(n) space due to recursion and adjacency storage. A similar strategy works with Breadth-First Search.

Recommended for interviews: Union-Find is often the expected solution because it directly models the two properties of a tree: no cycles and a single connected component. The n - 1 edge rule quickly filters invalid cases, and cycle detection becomes a constant-time check with find(). DFS demonstrates strong graph fundamentals and works well when you already need an adjacency list for traversal problems. Showing both approaches signals that you understand both connectivity checks and graph traversal patterns.