Graph Valid Tree — Solution in Python, Java & C++
Graph Valid Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Graph Valid Tree is a medium coding problem on depth-first search, breadth-first search and graph, asked in Amazon, Google, Meta and LinkedIn interviews.
- Difficulty: Medium
- Topics: Depth-First Search, Breadth-First Search, Graph, Union Find
- Asked at: Amazon, Google, Meta, LinkedIn
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You have n nodes labelled 0 through n - 1 and a list of undirected edges.
Return true if these edges make a valid tree — connected and acyclic.
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
Explanation: There is a cycle.
Example 3
Input: n = 4, edges = [[0,1],[2,3]]
Output: false
Explanation: Not connected.
Constraints
1 <= n <= 400 <= edges.length <= 60There are no duplicate edges and no self-loops.
Hints for Graph Valid Tree
Hint 1
A tree on
nnodes has exactlyn - 1edges — check that first and you rule out most inputs immediately.Hint 2
With the right edge count, connected and acyclic become the same condition.
Hint 3
So union the edges and reject the moment one joins two nodes already in the same set.
How to solve Graph Valid Tree
A tree on n nodes has exactly n - 1 edges; with that count, connected and acyclic coincide, so union the edges and fail on the first one whose endpoints already share a root.
Approach
- Return
falseunlesslen(edges) == n - 1. - Union-find over the edges; return
falseif an edge joins two nodes already connected. - Return
true.
Why it works
n - 1 edges with no cycle is a spanning forest with exactly one component — a tree. A cycle is detected precisely when an edge's endpoints are already in the same set.
Complexity
- Time —
O(n · α(n)) - Space —
O(n)
Pitfalls
- Without the edge-count check you must additionally verify a single component at the end.
Reference solution
Python
def validTree(n: int, edges) -> bool:
if len(edges) != n - 1:
return False
parent = list(range(n))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
for a, b in edges:
ra, rb = find(a), find(b)
if ra == rb:
return False
parent[ra] = rb
return TrueJava
private static int findRoot(int[] parent, int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
public static boolean validTree(int n, int[][] edges) {
if (edges.length != n - 1) return false;
int[] parent = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
for (int[] e : edges) {
int a = findRoot(parent, e[0]);
int b = findRoot(parent, e[1]);
if (a == b) return false;
parent[a] = b;
}
return true;
}C++
static int findRoot(vector<int>& parent, int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
bool validTree(int n, vector<vector<int>>& edges) {
if ((int) edges.size() != n - 1) return false;
vector<int> parent(n);
for (int i = 0; i < n; i++) parent[i] = i;
for (const auto& e : edges) {
int a = findRoot(parent, e[0]);
int b = findRoot(parent, e[1]);
if (a == b) return false;
parent[a] = b;
}
return true;
}JavaScript
var validTree = function(n, edges) {
if (edges.length !== n - 1) return false;
const parent = [];
for (let i = 0; i < n; i++) parent.push(i);
const find = function(x) {
while (parent[x] !== x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
};
for (let i = 0; i < edges.length; i++) {
const a = find(edges[i][0]);
const b = find(edges[i][1]);
if (a === b) return false;
parent[a] = b;
}
return true;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Breadth-First Search (BFS)