Graph Valid Tree Leetcode Problem 261 [Python Solution]
Problem Overview
In this blog post, we will tackle the Graph Valid Tree problem, a LeetCode problem number 261. This problem falls under the category of graphs and is of medium difficulty.
It's also a problem that companies like Facebook might use during their interviews.
You can find the original question on LintCode.
Question: Given n nodes labeled from 0 to n - 1 and a list of undirected edges, your task is to write a function to check whether these edges make up a valid tree.
You can assume that no duplicate edges will appear in the list of edges, and since all edges are undirected, [0, 1] is considered the same as [1, 0], and these duplicates will not appear together in the list of edges.
Example:
Let's consider two examples to illustrate the problem:
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
In the first example, the edges form a valid tree, while in the second example, they do not.
Problem Analysis
A valid tree has two essential characteristics:
- It must not contain any cycles (loops).
- Every node must be connected, meaning you can reach any node from any other node.
To solve this problem, we will perform a Depth-First Search (DFS) traversal on the graph to check these two conditions.
Understanding Constraints
Before we delve into the solution, let's understand some key concepts and constraints:
- A graph is a collection of nodes connected by edges.
- Undirected edges are connections between nodes that can be traversed in both directions.
- A tree is a special type of graph with no cycles, and all nodes are connected.
- DFS is a graph traversal algorithm that explores as far as possible along each branch before backtracking.
Graph Valid Tree LeetCode Problem Solution
Bruteforce Approach
We can use Depth-First Search (DFS) to traverse the graph and check if it satisfies the conditions of a valid tree.
Here's the Python solution:
def validTree(n, edges):
if not n:
return True
adj = {i: [] for i in range(n)}
for n1, n2 in edges:
adj[n1].append(n2)
adj[n2].append(n1)
visit = set()
def dfs(i, prev):
if i in visit:
return False
visit.add(i)
for j in adj[i]:
if j == prev:
continue
if not dfs(j, i):
return False
return True
return dfs(0, -1) and n == len(visit)
This code defines a validTree function that takes the number of nodes (n) and a list of undirected edges (edges) as input.
It uses DFS to traverse the graph, keeping track of visited nodes to check for cycles and ensuring all nodes are connected.
If both conditions are met, the function returns True, indicating that the graph is a valid tree.
Efficient Approach with Disjoint Set Union (DSU)
An alternative approach is to use Disjoint Set Union (DSU) to check for cycles and connectivity more efficiently.
The time complexity of this approach is O(ElogV), where E is the number of edges, and V is the number of vertices.
Here's the Python solution:
class Solution:
def __find(self, n: int) -> int:
while n != self.parents.get(n, n):
n = self.parents.get(n, n)
return n
def __connect(self, n: int, m: int) -> None:
pn = self.__find(n)
pm = self.__find(m)
if pn == pm:
return
if self.heights.get(pn, 1) > self.heights.get(pm, 1):
self.parents[pn] = pm
else:
self.parents[pm] = pn
self.heights[pm] = self.heights.get(pn, 1) + 1
self.components -= 1
def valid_tree(self, n: int, edges: List[List[int]) -> bool:
self.parents = {}
self.heights = {}
self.components = n
for e1, e2 in edges:
if self.__find(e1) == self.__find(e2): # 'redundant' edge
return False
self.__connect(e1, e2)
return self.components == 1 # The forest contains one tree
This code defines a Solution class with an efficient approach using DSU.
The valid_tree function checks for cycles and connectivity, returning True if the graph forms a valid tree.
Time and Space Complexity
Bruteforce Approach:
- Time Complexity:
O(E + V), where E is the number of edges, and V is the number of vertices. - Space Complexity:
O(V), as we use a set to store visited nodes.
Efficient Approach with DSU:
- Time Complexity:
O(ElogV), where E is the number of edges, and V is the number of vertices. - Space Complexity:
O(V), as we use DSU to track components.
Reasoning Behind Our Approach
We've discussed two approaches to solve the Graph Valid Tree problem:
- The bruteforce approach uses Depth-First Search (DFS) to traverse the graph, keeping track of visited nodes to check for cycles and ensuring all nodes are connected.
This approach provides a clear and easy-to-understand solution.
- The efficient approach with Disjoint Set Union (DSU) provides a more optimized solution.
DSU helps us detect cycles and connectivity more efficiently, reducing the time complexity.
Both approaches are valid, and you can choose the one that suits your needs and understanding of the problem.
In summary, the Graph Valid Tree problem involves checking if a given set of nodes and edges form a valid tree.
You need to consider both cycle detection and connectivity to determine the validity of the tree.
Related Interview Questions By Company:
Related Interview Questions By Difficulty:
- Snakes And Ladders LeetCode
- Pacific Atlantic Water Flow LeetCode
- Shortest Path In Binary Matrix LeetCode
Conclusion
In this blog post, we explored the Graph Valid Tree problem, a LeetCode problem number 261. We discussed two approaches to solving this problem: a bruteforce approach using Depth-First Search (DFS) and an efficient approach using Disjoint Set Union (DSU).
Remember that a valid tree must not contain cycles (loops) and should have all nodes connected.
Both solutions presented here aim to satisfy these conditions.
You can choose the approach that best suits your requirements.
If you found this blog post helpful, please like and engage for more coding challenges and algorithm explanations.
Feel free to comment, ask questions, make suggestions, and share the content with
