How do you approach Graph Valid Tree?

A tree on n nodes has exactly n - 1 edges - reject anything else immediately.

What are common mistakes on Graph Valid Tree?

Building the adjacency list in one direction on an undirected graph. Assuming the graph is connected. Most inputs allow several components, and one traversal from node 0 misses the rest. Ignoring self-loops and parallel edges when the constraints allow them.

Sitelet https://gitgood.dev/coding/graph-valid-tree

gitGood.dev

← Back to problems

Graph Valid Tree

MediumAlgorithms

Description

Given n nodes labeled 0 to n - 1 and a list of undirected edges, determine whether these edges form a valid tree.

A valid tree is connected and contains no cycles.

Example 1

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

Output: true

Explanation: Connected and acyclic.

Example 2

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

Output: false

Explanation: Contains a cycle 1-2-3-1.

Constraints

- 1 <= n <= 2000 - 0 <= edges.length <= 5000 - No self-loops or duplicate edges

Graph Valid Tree: approach, complexity and pitfalls

A medium graphs problem, graded against 7 test cases (5 of them hidden).

The pattern: Graphs

Nodes and edges - traversal, connectivity, cycles, and shortest paths.

Reach for it when you see: Explicit edges, a grid treated as a graph, or dependencies between items.

If you are stuck

Show the 2-step hint ladder

A tree on n nodes has exactly n - 1 edges - reject anything else immediately.
With n - 1 edges, the graph is a tree iff it has no cycle (which union-find detects).

The optimal approach

Show the approach: The approach

Edge count + Union-Find. A tree must have exactly `n - 1` edges. Given that, union each edge; if any edge connects two nodes already in the same set, there is a cycle -> not a tree. `n - 1` edges with no cycle guarantees connectivity.

Time: O(n·α(n)). Space: O(n).

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Empty input. At least one case passes an empty collection. Make sure your loop bounds and any "first element" read survive a length of zero.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Graphs mistakes

These apply to the pattern as a whole, not just this problem.

Building the adjacency list in one direction on an undirected graph.
Assuming the graph is connected. Most inputs allow several components, and one traversal from node 0 misses the rest.
Ignoring self-loops and parallel edges when the constraints allow them.