Graph Valid Tree
FreeGraphsMedium46 of 75
The problem
Given n ≥ 1 vertices labeled 0 through n−1 and undirected edges without self-loops or duplicate edges, decide whether the graph is one tree.
Example
n = 4, edges = [[0, 1], [1, 2], [1, 3]] → true
Need a hint?
A tree is connected and has exactly n−1 edges.
Write pseudocode, trace the example, or note an edge case. This scratchpad does not run code.
Notes stay in this browser when storage is available.
Read the solution approach
Reject any edge count other than n−1. Build adjacency lists and traverse from vertex 0, marking each vertex once. Accept only if all n vertices are reached. With n−1 edges, connectivity also rules out cycles.
Complexity
O(n + E) time and space.
Before moving on, explain why the algorithm is correct and trace a boundary case without looking at the approach.