Graph Valid Tree

Problem Description

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] = [a, b] indicates that there is an undirected edge between nodes a and b in the graph.

Return true if the edges of the given graph make up a valid tree, and false otherwise.

Examples

Constraints

• 1 ≤ n ≤ 2000
• 0 ≤ edges.length ≤ 5000
• edges[i].length == 2
• 0 ≤ a, b < n
• a != b
• There are no self-loops or duplicate edges.

Checking for Connectivity and Cycle-Free Structures

By definition, a graph is a valid tree if and only if:

1. It is fully connected (there is a path between every pair of nodes).
2. It contains no cycles.

We can check both properties using Union-Find.

• We start with n disconnected nodes.
• For each edge [a, b], we check if a and b are already connected (their root representatives are identical). If they are, adding this edge creates a cycle, so we return false immediately.
• If they are not connected, we union their sets, merging the components.
• After processing all edges, the graph is a valid tree only if no cycles were found and all nodes are merged into a single connected component (meaning the number of union operations was exactly n - 1).

Solution 1: Union-Find (Disjoint Set Union)

Initialize parent pointers and ranks. Detect cycles during unions, and check final connectivity.

class Solution {
    public boolean validTree(int n, int[][] edges) {
        // A tree with n nodes must have exactly n - 1 edges
        if (edges.length != n - 1) return false;

        int[] parent = new int[n];
        int[] rank = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 1;
        }

        for (int[] edge : edges) {
            if (!union(edge[0], edge[1], parent, rank)) {
                return false; // cycle detected
            }
        }
        return true; // since edge count is n - 1 and no cycle, it must be connected
    }

    private int find(int val, int[] parent) {
        int curr = val;
        while (curr != parent[curr]) {
            parent[curr] = parent[parent[curr]]; // path compression
            curr = parent[curr];
        }
        return curr;
    }

    private boolean union(int n1, int n2, int[] parent, int[] rank) {
        int p1 = find(n1, parent);
        int p2 = find(n2, parent);

        if (p1 == p2) return false; // already connected, adding this edge creates a cycle

        if (rank[p1] > rank[p2]) {
            parent[p2] = p1;
            rank[p1] += rank[p2];
        } else {
            parent[p1] = p2;
            rank[p2] += rank[p1];
        }
        return true;
    }
}

class Solution:
    def validTree(self, n: int, edges: list[list[int]]) -> bool:
        # A tree with n nodes must have exactly n - 1 edges
        if len(edges) != n - 1:
            return False

        parent = list(range(n))
        rank = [1] * n

        def find(val):
            curr = val
            while curr != parent[curr]:
                parent[curr] = parent[parent[curr]]  # path compression
                curr = parent[curr]
            return curr

        def union(n1, n2):
            p1, p2 = find(n1), find(n2)
            if p1 == p2:
                return False  # already connected, adding this edge creates a cycle

            if rank[p1] > rank[p2]:
                parent[p2] = p1
                rank[p1] += rank[p2]
            else:
                parent[p1] = p2
                rank[p2] += rank[p1]
            return True

        for n1, n2 in edges:
            if not union(n1, n2):
                return False  # cycle detected

        return True

#include <vector>
#include <numeric>

class Solution {
private:
    int find(int val, std::vector<int>& parent) {
        int curr = val;
        while (curr != parent[curr]) {
            parent[curr] = parent[parent[curr]]; // path compression
            curr = parent[curr];
        }
        return curr;
    }

    bool unionNodes(int n1, int n2, std::vector<int>& parent, std::vector<int>& rank) {
        int p1 = find(n1, parent);
        int p2 = find(n2, parent);

        if (p1 == p2) return false; // already connected, cycle detected

        if (rank[p1] > rank[p2]) {
            parent[p2] = p1;
            rank[p1] += rank[p2];
        } else {
            parent[p1] = p2;
            rank[p2] += rank[p1];
        }
        return true;
    }

public:
    bool validTree(int n, std::vector<std::vector<int>>& edges) {
        // A tree with n nodes must have exactly n - 1 edges
        if (edges.size() != n - 1) return false;

        std::vector<int> parent(n);
        std::iota(parent.begin(), parent.end(), 0);
        std::vector<int> rank(n, 1);

        for (const auto& edge : edges) {
            if (!unionNodes(edge[0], edge[1], parent, rank)) {
                return false; // cycle detected
            }
        }
        return true;
    }
};

Complexity Analysis:

• Time Complexity: O(N * α(N)) which is effectively O(N) linear time, where N is the number of nodes. Union-Find with rank and path compression takes amortized constant time per operation.
• Space Complexity: O(N) to store parent and rank arrays.

Where it breaks: Nothing breaks for undirected graph cycle detection. If the edge count check edges.length == n - 1 is omitted, a graph consisting of isolated nodes and a small cycle (e.g. n = 5, edges = [[0,1],[1,0]]) could return incorrect results. The edge count check is a critical safeguard.

Common Mistakes

• Omitting the edges.length == n - 1 early check. A tree must have exactly n - 1 edges. If it has fewer, it is disconnected; if it has more, it must contain a cycle. Checking this upfront simplifies the algorithm.
• Not implementing path compression. If omitted, find operations degrade to linear time.
• Treating directed and undirected cycle detection the same. This is an undirected graph, so Union-Find is perfect. For directed graphs, you must use DFS with path tracking.

Frequently Asked Questions

Can we solve this using DFS? Yes. You can build an adjacency list and run DFS starting at node 0. Track visited nodes. If you encounter an already visited node that is not the direct parent of the current node, a cycle exists. After DFS, check if the visited set size equals n.

Why does edges.length != n - 1 guarantee disconnection if no cycle is found? By graph theory, any acyclic graph with n nodes and n - 1 edges is guaranteed to be fully connected. Checking edges.length == n - 1 and verifying no cycle is sufficient.

What does this problem test in interviews? It tests your knowledge of tree definitions, graph properties, and cycle detection using Union-Find or traversal.

← All Problems