Is Graph Valid Tree easy or hard?

Graph Valid Tree is generally classified as a medium-level problem. The difficulty comes from recognizing the two defining properties of a tree—exactly n-1 edges and no cycles—then applying either Union-Find or graph traversal correctly.

Graph Valid Tree Python/Java solution

Python and Java implementations typically use either Union-Find with parent and rank arrays or DFS with an adjacency list and visited set. Both implementations achieve O(n) time complexity and are straightforward to implement for interview settings.

How to solve Graph Valid Tree in O(n)?

Start by checking that the number of edges equals n-1. Then use Union-Find to process edges and detect cycles, or run a DFS/BFS traversal to ensure the graph is connected and acyclic. Both strategies visit each node and edge at most once, giving O(n) time complexity.

What is the best approach for Graph Valid Tree?

Union-Find is the most common and interview-friendly approach. It quickly detects cycles while merging connected components and runs in O(n) time with O(n) space. Combined with the rule that a valid tree must have exactly n-1 edges, it efficiently verifies both connectivity and acyclicity.

Is Graph Valid Tree asked at Google/Amazon/Meta?

Graph connectivity and cycle detection problems like Graph Valid Tree frequently appear in interviews at companies such as Google, Amazon, and Meta. They test understanding of graph traversal, Union-Find structures, and the structural properties that define trees.

What data structure is used in Graph Valid Tree?

Common data structures include the Union-Find (Disjoint Set) structure for component tracking and adjacency lists for DFS or BFS traversal. Union-Find efficiently merges sets and checks cycles, while adjacency lists support standard graph traversal algorithms.

What is the time complexity of Graph Valid Tree?

The optimal solutions run in O(n) time where n is the number of nodes. Union-Find processes each edge with near-constant amortized cost, while DFS or BFS traverses each node and edge once. Space complexity is O(n) for storing parent arrays or adjacency lists.

Description Hints 2 Solution Video 14:11

261. Graph Valid Tree

Medium49.9% acceptance9 companiesPremium elsewhere, free here

You have a graph of n nodes labeled from 0 to n - 1. You are given an integer n and a list of edges where edges[i] = [a_i, b_i] indicates that there is an undirected edge between nodes a_i and b_i in the graph.

Return true if the edges of the given graph make up a valid tree, and false otherwise.

Example 1:

Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
Output: true

Example 2:

Input: n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]
Output: false

Constraints:

1 <= n <= 2000
0 <= edges.length <= 5000
edges[i].length == 2
0 <= a_i, b_i < n
a_i != b_i
There are no self-loops or repeated edges.

Asked at 9 companies

Zenefits Snowflake LinkedIn

Google Meta Uber Tiktok Amazon Microsoft

Topics

Hints open one at a time

Hint 1

Given n = 5 and edges = [[0, 1], [1, 2], [3, 4]], what should your return? Is this case a valid tree?

Hint 2

According to the definition of tree on Wikipedia: “a tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.”

14:11

Still stuck?Read 2 approaches, or watch a walkthrough.

Open solution