Graph Valid Tree
Graph Valid Tree – Medium Level Problem
You are given n nodes labeled from 0 to n – 1 and a list of undirected edges. Write a function to determine if these edges form a valid tree.
To determine if the given edges form a valid tree, the graph must satisfy two conditions:
- Connected: All nodes must be reachable from any starting node, ensuring there is no isolated component.
- Acyclic: The graph must not contain any cycles, as a tree cannot have loops.
An integer k is also provided, representing the starting node for the signal.
Tips:
You can use graph traversal methods like Depth-First Search (DFS), Breadth-First Search (BFS), or Union-Find to verify these conditions.
If both are satisfied, the graph represents a valid tree.
If both are satisfied, the graph represents a valid tree.
Examples related to Graph Valid Tree Problem
Example 1:
Input:
n = 5
edges = [[0, 1], [0, 2], [0, 3], [1, 4]]
Output: true
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
edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]
Output: false
Note:
You can assume there are no duplicate edges in the list.
Since all edges are undirected, [0, 1] is equivalent to [1, 0] and will not appear twice in the list.
Since all edges are undirected, [0, 1] is equivalent to [1, 0] and will not appear twice in the list.
Constraints:
- 1 <= n <= 100
- 0 <= edges.length <= n * (n – 1) / 2
Hints to solve Graph Valid Tree Problem
Recommended Time & Space Complexity
Aim for a solution with O(V + E) time and O(V + E) space, where V is the number of vertices and E is the number of edges.
Hint 1:
A tree is defined as an undirected graph that is fully connected (one component), contains no cycles, and has exactly V – 1 edges.
To validate the input graph as a tree, we need to ensure these properties.
Can you think of a recursive algorithm to check for cycles while ensuring connectivity?
Hint 2:
Use Depth First Search (DFS) to detect cycles in the graph. Start DFS from any node (e.g., node 0) and recursively visit its neighbors.
If a visited node is encountered and it is not the parent of the current node, it indicates a cycle.
If no cycles are found and all nodes are visited, the graph is a tree.
How would you implement this?
Hint 3:
Begin DFS from node 0, treating its parent as -1. Use a set to track visited nodes.
For each node, if it’s already in the set, return false to indicate a cycle. Otherwise, mark it as visited and continue DFS for its neighbors, skipping the parent.
After DFS completes, check if all nodes are visited to ensure the graph is connected. If any node is unvisited, the graph is not a tree.
Methods to Solve Graph Valid Tree Problem
There are mainly 3 approaches to solve Graph Valid Tree problem:
- Cycle Detection (DFS)
- Breadth First Search
- Disjoint Set Union
1. Cycle Detection (DFS) Method
Use Depth First Search to check if the graph has any cycles. Start from any node, and as you traverse, track visited nodes and their parents. If you revisit a node that’s not the parent, it indicates a cycle. Ensure all nodes are connected by checking if all nodes are visited.
- Time complexity: O(V+E)
- Space complexity: O(V+E)
Where V is the number of vertices and E is the number of edges.
Code:
C++
Java
Python
JavaScript
C++
class Solution {
public:
bool validTree(int n, vector>& edges) {
if (edges.size() > n - 1) {
return false;
}
vector> adj(n);
for (const auto& edge : edges) {
adj[edge[0]].push_back(edge[1]);
adj[edge[1]].push_back(edge[0]);
}
unordered_set visit;
if (!dfs(0, -1, visit, adj)) {
return false;
}
return visit.size() == n;
}
private:
bool dfs(int node, int parent, unordered_set& visit,
vector>& adj) {
if (visit.count(node)) {
return false;
}
visit.insert(node);
for (int nei : adj[node]) {
if (nei == parent) {
continue;
}
if (!dfs(nei, node, visit, adj)) {
return false;
}
}
return true;
}
};
Java
public class Solution {
public boolean validTree(int n, int[][] edges) {
if (edges.length > n - 1) {
return false;
}
List> adj = new ArrayList<>();
for (int i = 0; i < n; i++) {
adj.add(new ArrayList<>());
}
for (int[] edge : edges) {
adj.get(edge[0]).add(edge[1]);
adj.get(edge[1]).add(edge[0]);
}
Set visit = new HashSet<>();
if (!dfs(0, -1, visit, adj)) {
return false;
}
return visit.size() == n;
}
private boolean dfs(int node, int parent, Set visit,
List> adj) {
if (visit.contains(node)) {
return false;
}
visit.add(node);
for (int nei : adj.get(node)) {
if (nei == parent) {
continue;
}
if (!dfs(nei, node, visit, adj)) {
return false;
}
}
return true;
}
}
Python
class Solution:
def validTree(self, n: int, edges: List[List[int]]) -> bool:
if len(edges) > (n - 1):
return False
adj = [[] for _ in range(n)]
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
visit = set()
def dfs(node, par):
if node in visit:
return False
visit.add(node)
for nei in adj[node]:
if nei == par:
continue
if not dfs(nei, node):
return False
return True
return dfs(0, -1) and len(visit) == n
JavaScript
class Solution {
/**
* @param {number} n
* @param {number[][]} edges
* @returns {boolean}
*/
validTree(n, edges) {
if (edges.length > n - 1) {
return false;
}
const adj = Array.from({ length: n }, () => []);
for (const [u, v] of edges) {
adj[u].push(v);
adj[v].push(u);
}
const visit = new Set();
const dfs = (node, parent) => {
if (visit.has(node)) {
return false;
}
visit.add(node);
for (const nei of adj[node]) {
if (nei === parent) {
continue;
}
if (!dfs(nei, node)) {
return false;
}
}
return true;
};
return dfs(0, -1) && visit.size === n;
}
}
2. Breadth First Search
Use Breadth First Search to traverse the graph and check for cycles. Maintain a queue and track visited nodes. If you revisit a node that’s not the parent, it’s a cycle. After traversal, verify all nodes are connected for a valid tree.
- Time complexity: O(V + E)
- Space complexity: O(V + E)
Where V is the number of vertices and E is the number of edges.
Code:
C++
Java
Python
JavaScript
C++
class Solution {
public:
bool validTree(int n, vector>& edges) {
if (edges.size() > n - 1) {
return false;
}
vector> adj(n);
for (const auto& edge : edges) {
adj[edge[0]].push_back(edge[1]);
adj[edge[1]].push_back(edge[0]);
}
unordered_set visit;
queue> q;
q.push({0, -1}); // {current node, parent node}
visit.insert(0);
while (!q.empty()) {
auto [node, parent] = q.front();
q.pop();
for (int nei : adj[node]) {
if (nei == parent) {
continue;
}
if (visit.count(nei)) {
return false;
}
visit.insert(nei);
q.push({nei, node});
}
}
return visit.size() == n;
}
};
Java
public class Solution {
public boolean validTree(int n, int[][] edges) {
if (edges.length > n - 1) {
return false;
}
List> adj = new ArrayList<>();
for (int i = 0; i < n; i++) {
adj.add(new ArrayList<>());
}
for (int[] edge : edges) {
adj.get(edge[0]).add(edge[1]);
adj.get(edge[1]).add(edge[0]);
}
Set visit = new HashSet<>();
Queue q = new LinkedList<>();
q.offer(new int[]{0, -1}); // {current node, parent node}
visit.add(0);
while (!q.isEmpty()) {
int[] pair = q.poll();
int node = pair[0], parent = pair[1];
for (int nei : adj.get(node)) {
if (nei == parent) {
continue;
}
if (visit.contains(nei)) {
return false;
}
visit.add(nei);
q.offer(new int[]{nei, node});
}
}
return visit.size() == n;
}
}
Python
class Solution:
def validTree(self, n: int, edges: List[List[int]]) -> bool:
if len(edges) > n - 1:
return False
adj = [[] for _ in range(n)]
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
visit = set()
q = deque([(0, -1)]) # (current node, parent node)
visit.add(0)
while q:
node, parent = q.popleft()
for nei in adj[node]:
if nei == parent:
continue
if nei in visit:
return False
visit.add(nei)
q.append((nei, node))
return len(visit) == n
JavaScript
class Solution {
/**
* @param {number} n
* @param {number[][]} edges
* @returns {boolean}
*/
validTree(n, edges) {
if (edges.length > n - 1) {
return false;
}
const adj = Array.from({ length: n }, () => []);
for (const [u, v] of edges) {
adj[u].push(v);
adj[v].push(u);
}
const visit = new Set();
const q = new Queue([[0, -1]]); // [current node, parent node]
visit.add(0);
while (!q.isEmpty()) {
const [node, parent] = q.pop();
for (const nei of adj[node]) {
if (nei === parent) continue;
if (visit.has(nei)) return false;
visit.add(nei);
q.push([nei, node]);
}
}
return visit.size === n;
}
}
3. Disjoint Set Union
Use Union-Find to check for cycles and connectivity. For every edge, check if the two nodes belong to the same set (indicating a cycle). If not, union them. After processing all edges, ensure exactly one connected component for a valid tree.
- Time complexity: O(V+(E∗α(V)))
- Space complexity: O(V)
Where V is the number of vertices and E is the number of edges.
Code:
C++
Java
Python
JavaScript
C++
class DSU {
vector Parent, Size;
int comps;
public:
DSU(int n) {
comps = n;
Parent.resize(n + 1);
Size.resize(n + 1);
for (int i = 0; i <= n; i++) {
Parent[i] = i;
Size[i] = 1;
}
}
int find(int node) {
if (Parent[node] != node) {
Parent[node] = find(Parent[node]);
}
return Parent[node];
}
bool unionNodes(int u, int v) {
int pu = find(u), pv = find(v);
if (pu == pv) return false;
if (Size[pu] < Size[pv]) {
swap(pu, pv);
}
comps--;
Size[pu] += Size[pv];
Parent[pv] = pu;
return true;
}
int components() {
return comps;
}
};
class Solution {
public:
bool validTree(int n, vector>& edges) {
if (edges.size() > n - 1) {
return false;
}
DSU dsu(n);
for (auto& edge : edges) {
if (!dsu.unionNodes(edge[0], edge[1])) {
return false;
}
}
return dsu.components() == 1;
}
};
Java
public class DSU {
int[] Parent, Size;
int comps;
public DSU(int n) {
comps = n;
Parent = new int[n + 1];
Size = new int[n + 1];
for (int i = 0; i <= n; i++) {
Parent[i] = i;
Size[i] = 1;
}
}
public int find(int node) {
if (Parent[node] != node) {
Parent[node] = find(Parent[node]);
}
return Parent[node];
}
public boolean union(int u, int v) {
int pu = find(u), pv = find(v);
if (pu == pv) return false;
if (Size[pu] < Size[pv]) {
int temp = pu;
pu = pv;
pv = temp;
}
comps--;
Size[pu] += Size[pv];
Parent[pv] = pu;
return true;
}
public int components() {
return comps;
}
}
public class Solution {
public boolean validTree(int n, int[][] edges) {
if (edges.length > n - 1) {
return false;
}
DSU dsu = new DSU(n);
for (int[] edge : edges) {
if (!dsu.union(edge[0], edge[1])) {
return false;
}
}
return dsu.components() == 1;
}
}
Python
class DSU:
def __init__(self, n):
self.comps = n
self.Parent = list(range(n + 1))
self.Size = [1] * (n + 1)
def find(self, node):
if self.Parent[node] != node:
self.Parent[node] = self.find(self.Parent[node])
return self.Parent[node]
def union(self, u, v):
pu = self.find(u)
pv = self.find(v)
if pu == pv:
return False
self.comps -= 1
if self.Size[pu] < self.Size[pv]:
pu, pv = pv, pu
self.Size[pu] += self.Size[pv]
self.Parent[pv] = pu
return True
def components(self):
return self.comps
class Solution:
def validTree(self, n: int, edges: List[List[int]]) -> bool:
if len(edges) > n - 1:
return False
dsu = DSU(n)
for u, v in edges:
if not dsu.union(u, v):
return False
return dsu.components() == 1JavaScript
class DSU {
constructor(n) {
this.comps = n;
this.Parent = Array.from({ length: n + 1 }, (_, i) => i);
this.Size = Array(n + 1).fill(1);
}
/**
* @param {number} node
* @return {number}
*/
find(node) {
if (this.Parent[node] !== node) {
this.Parent[node] = this.find(this.Parent[node]);
}
return this.Parent[node];
}
/**
* @param {number} u
* @param {number} v
* @return {boolean}
*/
union(u, v) {
let pu = this.find(u);
let pv = this.find(v);
if (pu === pv) return false;
if (this.Size[pu] < this.Size[pv]) {
[pu, pv] = [pv, pu];
}
this.comps--;
this.Size[pu] += this.Size[pv];
this.Parent[pv] = pu;
return true;
}
/**
* @return {number}
*/
components() {
return this.comps;
}
}
class Solution {
/**
* @param {number} n
* @param {number[][]} edges
* @returns {boolean}
*/
validTree(n, edges) {
if (edges.length > n - 1) {
return false;
}
const dsu = new DSU(n);
for (const [u, v] of edges) {
if (!dsu.union(u, v)) {
return false;
}
}
return dsu.components() === 1;
}
}
