Graph Valid Tree

Graph Valid Tree refers to LeetCode problem 261, commonly asked in LinkedIn interviews with DFS, BFS, and Union Find approaches.[1][2]

Problem Statement

Given n nodes labeled from 0 to n-1 and a list of undirected edges representing a graph, determine if this graph forms a valid tree. A valid tree must be connected (exactly one connected component) and acyclic (no cycles). Return true if it is a valid tree, false otherwise.[2][6][1]

Key Properties Checked

• Exactly n-1 edges for n nodes.
• All nodes form a single connected component.
• No cycles exist in the graph.[2]

Input/Output Examples

Example 1: Valid Tree

Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]] Output: true This forms a tree rooted at 0 with children 1,2,3 and 1 connected to 4. All nodes are connected with no cycles.[1][2]

Example 2: Invalid (Cycle)

Input: n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]] Output: false A cycle exists between nodes 1-2-3-1, violating the acyclic property.[1]

Example 3: Invalid (Disconnected)

Input: n = 5, edges = [[0,1],[0,2],[0,3]] Output: false Node 4 is isolated, creating multiple connected components.[1]

Constraints

• 1 <= n <= 10^4
• 0 <= edges.length <= max(n^2, n-1)
• edges[i].length == 2
• 0 <= a_i, b_i < n
• a_i != b_i
• No repeated edges (undirected graph with unique pairs).[2]

Common Solution Approaches

Union Find (DSU): Initialize each node as its own parent. For each edge, if nodes share the same root (cycle), return false. After all edges, check for exactly one component and n-1 edges.[2]

DFS/BFS: Build adjacency list, check connectivity from node 0 (visiting all n nodes), and detect cycles via back edges (excluding parent in undirected graph).[1][2]