Valid Tree
Application of Union Find / Disjoint Set Union Data Structure

Algorithms and Data Structures: TheAlgorist.com

System Design: www.System.Design

Low Level Design: LowLevelDesign.io

Frontend Engineering: FrontendEngineering.io
জয় শ্রী রাম
🕉
Problem Statement:
You have a graph of n nodes labeled from 0 to n  1. You are given an integer n and a list of edges where edges[i] = [ai, bi] indicates that there is an undirected edge between nodes ai and bi in the graph.
Return true if the edges of the given graph make up a valid tree, and false otherwise.
Example 1:
0 /  \ 1 2 3  4
Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
Output: true
Example 2:
0  1  2  \ / 4 3
Input: n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]
Output: false
Solution:
This problem is part of UnionFind Series, so please be sure to go through each and every chapter in the series in order to have a solid understand of UnionFind and become really good at solving problems using UnionFind.
 Prerequisite: Union Find Fundamentals
A valid tree won't have any cycle. So the problem reduces to finding cycle. All the connected nodes would go to same connected component or disjoint set. If there is an edge between two nodes which already belong to same component then that edge would introduce a cycle in that connected component. For more details, please see 4 Ways to Finding Cycles
Union Find would be a very efficient data structure to solve this problem. We would iterate over the given edges array and go on unionizing the connected nodes. At any point of time if we find that we have connectivity between two nodes which have same root (i.e, they belong to the same set) we would know that there is a cycle and return false as this won't be a valid tree.
Java Code:
Login to Access Content
Python Code:
Login to Access Content
Complexity Analysis:
Time Complexity: O(N . InverseAckermann(N)) = O(N) since InverseAckermann(N) = O(1) approximately
Space Complexity: O(N), since we need to store all nodes in the unionfind data structure. We would have O(2N) nodes since N edges would have 2 nodes one on each side. So we could have at most 2 * N nodes.
N = number of edges
Please be sure to take a serious look at all the problems discussed
in Union Find Problems
to become from good to GREAT in solving problems using
UnionFind .
Instructor:
If you have any feedback, please use this form: https://thealgorists.com/Feedback.