Log inSign up
mediumLeetCodeNot Started

Is Graph a Tree

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Graph
Solve on LeetCode
Lesson

Problem Statement

### Problem Statement

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), determine whether these edges make up a valid tree.

An undirected graph with n nodes is a valid tree if and only if: 1. It is fully connected (there is a path between every pair of vertices). 2. It is acyclic (it contains no cycles).

---

### Examples

Example 1: ``text Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]] 0 / | \ 1 2 3 | 4 Output: true Explanation: The graph is connected and contains no cycles.

Example 2: ``text Input: n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]] 0 --- 1 --- 2 | \ / 4 3 Output: false Explanation: Nodes 1, 2, and 3 form a cycle (1 -> 2 -> 3 -> 1).

---

### Constraints - 1 <= n <= 2000 - 0 <= edges.length <= 5000 - edges[i].length == 2 - 0 <= ai, bi < n - ai != bi - There are no self-loops or duplicate edges.

Constraints:

  • 1 <= n <= 2000
  • 0 <= edges.length <= 5000
  • edges[i].length == 2
  • 0 <= ai, bi < n
  • No self-loops or duplicate edges

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Apply the graph tree equivalence theorem (|E| == V - 1 and connected).
  • Use Disjoint Set Union (DSU) to check cycle freedom and component unification.
  • Implement BFS/DFS connectivity validation with parent tracking.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Determine if an undirected graph forms a valid tree
  • Network connectivity with zero redundancy
  • Check acyclic and fully connected properties simultaneously

Algorithmic Decision Tree:

  • First check: if (edges.length != n - 1) return false;
  • Then check connectivity or acyclicity via DSU, BFS, or DFS.
  • If all n nodes visited and no cycles -> Valid tree.

Connected Patterns:

Number of Connected Components in an Undirected GraphRedundant ConnectionMinimum Spanning Tree (Kruskal's Algorithm)

1. Iterative BFS with Parent Tracking & Visited Count

Intuition

Starting from vertex 0, push (0, -1) into a queue. If any neighbor is already visited and not equal to the parent, a cycle exists. After the queue empties, if the number of visited nodes equals n, the graph is connected and acyclic.

Algorithm

  1. If edges.length != n - 1, return false.
  2. Build adjacency list for all n vertices.
  3. Initialize visited array of size n to false.
  4. Queue q pushes (0, -1); visited[0] = true.
  5. Initialize visitedCount = 0.
  6. While queue is not empty:
  7. Pop (curr, parent) from q, visitedCount++.
  8. For each neighbor in adj[curr]:
  9. If !visited[neighbor]:
  10. visited[neighbor] = true, q.push((neighbor, curr)).
  11. Else if neighbor != parent:
  12. Return false (cycle).
  13. Return visitedCount == n.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4
5class Solution {
6public:
7 bool validTree(int n, std::vector<std::vector<int>>& edges) {
8 if (edges.size() != n - 1) return false;
9
10 std::vector<std::vector<int>> adj(n);
11 for (const auto& e : edges) {
12 adj[e[0]].push_back(e[1]);
13 adj[e[1]].push_back(e[0]);
14 }
15
16 std::vector<bool> visited(n, false);
17 std::queue<std::pair<int, int>> q;
18 q.push({0, -1});
19 visited[0] = true;
20 int visitedCount = 0;
21
22 while (!q.empty()) {
23 auto [curr, parent] = q.front();
24 q.pop();
25 visitedCount++;
26
27 for (int neighbor : adj[curr]) {
28 if (!visited[neighbor]) {
29 visited[neighbor] = true;
30 q.push({neighbor, curr});
31 } else if (neighbor != parent) {
32 return false; // Cycle detected
33 }
34 }
35 }
36
37 return visitedCount == n;
38 }
39};
40
41int main() {
42 Solution sol;
43 std::vector<std::vector<int>> e1 = {{0,1},{0,2},{0,3},{1,4}};
44 std::vector<std::vector<int>> e2 = {{0,1},{1,2},{2,3},{1,3},{1,4}};
45 std::cout << "Tree 1: " << (sol.validTree(5, e1) ? "true" : "false") << " (Expected: true)\n";
46 std::cout << "Tree 2: " << (sol.validTree(5, e2) ? "true" : "false") << " (Expected: false)\n";
47 return 0;
48}

Time & Space Complexity

  • Time complexity: O(n)
  • Space complexity: O(n)

2. Recursive DFS with Component Count

Intuition

Because edges.length == n - 1 is established upfront, we only need to verify that the graph is connected. A simple recursive DFS starting from vertex 0 marks all reachable vertices. If the count of visited vertices equals n, it is guaranteed to be a valid tree.

Algorithm

  1. If edges.length != n - 1, return false.
  2. Build adjacency list adj.
  3. Initialize visited array of size n to false.
  4. Define dfs(u):
  5. visited[u] = true.
  6. For each neighbor v in adj[u]:
  7. If !visited[v]: dfs(v).
  8. Call dfs(0).
  9. For each vertex i from 0 to n - 1:
  10. If !visited[i]: return false.
  11. Return true.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class Solution {
5 void dfs(int u, const std::vector<std::vector<int>>& adj, std::vector<bool>& visited) {
6 visited[u] = true;
7 for (int v : adj[u]) {
8 if (!visited[v]) {
9 dfs(v, adj, visited);
10 }
11 }
12 }
13public:
14 bool validTree(int n, std::vector<std::vector<int>>& edges) {
15 if (edges.size() != n - 1) return false;
16
17 std::vector<std::vector<int>> adj(n);
18 for (const auto& e : edges) {
19 adj[e[0]].push_back(e[1]);
20 adj[e[1]].push_back(e[0]);
21 }
22
23 std::vector<bool> visited(n, false);
24 dfs(0, adj, visited);
25
26 for (int i = 0; i < n; ++i) {
27 if (!visited[i]) return false;
28 }
29 return true;
30 }
31};
32
33int main() {
34 Solution sol;
35 std::vector<std::vector<int>> e1 = {{0,1},{0,2},{0,3},{1,4}};
36 std::vector<std::vector<int>> e2 = {{0,1},{1,2},{2,3},{1,3},{1,4}};
37 std::cout << "DFS Tree 1: " << (sol.validTree(5, e1) ? "true" : "false") << "\n";
38 std::cout << "DFS Tree 2: " << (sol.validTree(5, e2) ? "true" : "false") << "\n";
39 return 0;
40}

Time & Space Complexity

  • Time complexity: O(n)
  • Space complexity: O(n)

3. Disjoint Set Union (DSU / Union-Find) (Optimal)

Intuition

The most elegant solution. Checking edges.length == n - 1 takes O(1) time. We then iterate through each edge with DSU. Since there are exactly n - 1 edges, if no cycle is ever formed (unite(u, v) succeeds for all edges), the graph MUST be both acyclic and fully connected (Euler's tree formula). No adjacency list construction required!

Algorithm

  1. If edges.length != n - 1, return false.
  2. Initialize DSU with n elements.
  3. For each edge [u, v] in edges:
  4. If !dsu.unite(u, v):
  5. Return false (cycle detected).
  6. Return true.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class DSU {
5 std::vector<int> parent, rank;
6public:
7 DSU(int n) : parent(n), rank(n, 0) {
8 for (int i = 0; i < n; ++i) parent[i] = i;
9 }
10 int find(int i) {
11 if (parent[i] == i) return i;
12 return parent[i] = find(parent[i]);
13 }
14 bool unite(int i, int j) {
15 int rootI = find(i);
16 int rootJ = find(j);
17 if (rootI != rootJ) {
18 if (rank[rootI] < rank[rootJ]) std::swap(rootI, rootJ);
19 parent[rootJ] = rootI;
20 if (rank[rootI] == rank[rootJ]) rank[rootI]++;
21 return true;
22 }
23 return false; // Cycle detected
24 }
25};
26
27class Solution {
28public:
29 bool validTree(int n, std::vector<std::vector<int>>& edges) {
30 if (edges.size() != n - 1) return false;
31
32 DSU dsu(n);
33 for (const auto& e : edges) {
34 if (!dsu.unite(e[0], e[1])) {
35 return false;
36 }
37 }
38 return true;
39 }
40};
41
42int main() {
43 Solution sol;
44 std::vector<std::vector<int>> e1 = {{0,1},{0,2},{0,3},{1,4}};
45 std::vector<std::vector<int>> e2 = {{0,1},{1,2},{2,3},{1,3},{1,4}};
46 std::cout << "DSU Valid Tree 1: " << (sol.validTree(5, e1) ? "true" : "false") << " (Expected: true)\n";
47 std::cout << "DSU Valid Tree 2: " << (sol.validTree(5, e2) ? "true" : "false") << " (Expected: false)\n";
48 return 0;
49}

Time & Space Complexity

  • Time complexity: O(n * alpha(n))
  • Space complexity: O(n)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Iterative BFS with Parent TrackingO(n)O(n)Guards edges.length == n - 1, builds adjacency list, checks cycle and count.Adjacency list allocation
2.Recursive DFS with Component CheckO(n)O(n)Guards edges.length == n - 1, then verifies full connectivity from root 0.Call stack depth
3.Disjoint Set Union (DSU / Union-Find)OptimalO(n * alpha(n))O(n)Guards edges.length == n - 1 and unions edges directly without building a graph.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Forgetting the O(1) check if (edges.length != n - 1) return false;.

Pitfall 2:

Only checking for absence of cycles without verifying that the graph is fully connected.

Pitfall 3:

Using directed graph cycle logic on undirected tree edges.

Crucial Edge Cases to Validate:

  • Single node with no edges (n = 1, edges = []) — edges.length == 0 == 1 - 1, DSU runs 0 edges, returns true (a single node is a valid tree).
  • Disconnected graph with n - 1 edges (e.g. triangle and isolated node) — DSU finds triangle cycle and returns false; DFS from 0 leaves isolated node unvisited and returns false.
  • More than n - 1 edges (e.g. 5 nodes and 5 edges) — edges.length == 5 != 4, immediately returns false in O(1) time.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State the tree invariant in your first sentence: 'A graph of n vertices is a tree if and only if it has exactly n - 1 edges AND is connected (or acyclic).'
  2. Highlight that checking edges.length == n - 1 upfront provides an immediate O(1) filter.
  3. Showcase the DSU solution to demonstrate that no adjacency list is needed.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does checking edges.length == n - 1 simplify graph valid tree verification?

2.What happens if a graph has n = 5 and edges = [[0, 1], [2, 3]]?

3.Why does the DSU approach not require constructing an adjacency list?

Back to DSA Sheet