261. Graph Valid Tree
Graph Valid Tree (LeetCode 261) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Union-Find (Disjoint Set Union - DSU) subpattern.
How to solve Graph Valid Tree
Graph Valid Tree is a Union-Find problem, part of Graph Traversal Patterns (DFS & BFS). Master Union-Find data structure with path compression and union by rank for connectivity problems.
Work towards the solution in these steps:
- Given <code>n = 5</code> and <code>edges = [[0, 1], [1, 2], [3, 4]]</code>, what should your return? Is this case a valid tree?
- According to the <a href="https://en.wikipedia.org/wiki/Tree_(graph_theory)" target="_blank">definition of tree on Wikipedia</a>: “a tree is an undirected graph in which any two vertices are connected by <i>exactly</i> one path. In other words, any connected graph without simple cycles is a tree.”
The reference solution runs in O(n + m) time and O(n + m) space.
The Graph Valid Tree solution and editorial walks through the full approach with reference code.
Problem statement
You are given an integer n, representing the number of nodes labeled from 0 to n - 1, and a list of undirected edges edges, where each edge is represented as a pair [a, b] indicating a connection between nodes a and b.
A graph is considered a valid tree if it is connected (there is a path between any two nodes) and acyclic (contains no cycles).
Return true if the given edges form a valid tree with n nodes, and false otherwise.
Examples
Example 1
Input: {"n": 5, "edges": [[0, 1], [0, 2], [0, 3], [1, 4]]}
Output: true
Explanation: The graph is connected and has exactly n-1 edges, so it is a valid tree.
Example 2
Input: {"n": 4, "edges": [[0, 1], [2, 3]]}
Output: false
Explanation: The graph is disconnected, so it cannot be a valid tree.
Topics and companies
Topics: Depth-First Search, Breadth-First Search, Union Find, Graph.
Reported in interviews at Amazon, Qualtrics, Microsoft.
How to practise Graph Valid Tree on Thita.ai
Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n + m) time and O(n + m) space.
Open Graph Valid Tree in the code editor, or read the Graph Valid Tree editorial for a worked solution with its approach and complexity analysis.
Where Graph Valid Tree sits in the DSA pattern sheet
- Graph Traversal Patterns (DFS & BFS) pattern guide
- Union-Find (Disjoint Set Union - DSU) subpattern
- The full DSA patterns sheet
Problems related to Graph Valid Tree
Other problems that use the same Union-Find (Disjoint Set Union - DSU) and Graph Traversal Patterns (DFS & BFS) techniques:
- Accounts Merge — Medium, same subpattern
- Greatest Common Divisor Traversal — Hard, same subpattern
- Largest Component Size by Common Factor — Hard, same subpattern
- Most Stones Removed with Same Row or Column — Medium, same subpattern
- Number of Connected Components in an Undirected Graph — Medium, same subpattern
- Number of Islands II — Hard, same subpattern
Graph Valid Tree FAQ
What is the LeetCode number of Graph Valid Tree?
Graph Valid Tree is LeetCode problem 261, rated Medium.
What pattern is used to solve Graph Valid Tree?
Graph Valid Tree is a Union-Find problem. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Union-Find (Disjoint Set Union - DSU) subpattern.
What is the time complexity of Graph Valid Tree?
The reference solution runs in O(n + m) time and O(n + m) space.
Which companies ask Graph Valid Tree?
Graph Valid Tree has been reported in interviews at Amazon, Qualtrics, Microsoft.