Graph Valid Tree

Medium · Graphs · Explanation and code example

Disjoint Set Union

How it works

A graph is a valid tree if:

  1. It has no cycles
  2. It is fully connected

Using Disjoint Set Union (Union-Find):

  • Each node starts in its own component
  • When we connect two nodes:
    • If they are already in the same component, adding this edge creates a cycle
    • Otherwise, we merge their components
  • In the end, a valid tree must have exactly one connected component

Also, a tree with n nodes can have at most n - 1 edges.

Steps

  1. If number of edges > n - 1, return false.
  2. Initialize DSU with n components.
  3. For each edge (u, v):
    • If union(u, v) fails → cycle detected → return false.
  4. After processing all edges:
    • Check if number of components is 1.
  5. Return true if only one component exists, else false.

Complexity

  • Time complexity: O(V + (E * α(V)))
  • Space complexity: O(V)

Where V is the number of vertices and E is the number of edges in the graph. α() is used for amortized complexity.

Things to watch for

Detecting False Cycles Due to Parent Edges

In an undirected graph represented with an adjacency list, each edge (u, v) appears twice: once in adj[u] and once in adj[v]. When traversing from node u to v, you will see u in v's neighbor list. Without tracking the parent, this would incorrectly be detected as a cycle. Always pass and check the parent node to avoid this false positive.

Forgetting to Check Connectivity

A graph can be cycle-free but still not be a valid tree if it is disconnected. After running DFS or BFS from any starting node, you must verify that all n nodes were visited. If visited.size() < n, the graph has multiple connected components and is not a valid tree.

Not Using the Edge Count Shortcut

A valid tree with n nodes must have exactly n - 1 edges. If there are more than n - 1 edges, the graph definitely has a cycle. If there are fewer than n - 1 edges, the graph cannot be connected. Checking this condition first can save unnecessary traversal and provides an early exit for invalid inputs.

Python code example

from typing import List

class DSU:
    def __init__(self, n):
        self.comps = n
        self.Parent = list(range(n + 1))
        self.Size = [1] * (n + 1)

    def find(self, node):
        if self.Parent[node] != node:
            self.Parent[node] = self.find(self.Parent[node])
        return self.Parent[node]

    def union(self, u, v):
        pu = self.find(u)
        pv = self.find(v)
        if pu == pv:
            return False

        self.comps -= 1
        if self.Size[pu] < self.Size[pv]:
            pu, pv = pv, pu
        self.Size[pu] += self.Size[pv]
        self.Parent[pv] = pu
        return True

    def components(self):
        return self.comps

class Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        if len(edges) > n - 1:
            return False

        dsu = DSU(n)
        for u, v in edges:
            if not dsu.union(u, v):
                return False
        return dsu.components() == 1

C++ code example

class DSU {
    vector<int> Parent, Size;
    int comps;
public:
    DSU(int n) {
        comps = n;
        Parent.resize(n + 1);
        Size.resize(n + 1);
        for (int i = 0; i <= n; i++) {
            Parent[i] = i;
            Size[i] = 1;
        }
    }

    int find(int node) {
        if (Parent[node] != node) {
            Parent[node] = find(Parent[node]);
        }
        return Parent[node];
    }

    bool unionNodes(int u, int v) {
        int pu = find(u), pv = find(v);
        if (pu == pv) return false;
        if (Size[pu] < Size[pv]) {
            swap(pu, pv);
        }
        comps--;
        Size[pu] += Size[pv];
        Parent[pv] = pu;
        return true;
    }

    int components() {
        return comps;
    }
};

class Solution {
public:
    bool validTree(int n, vector<vector<int>>& edges) {
        if (edges.size() > n - 1) {
            return false;
        }

        DSU dsu(n);
        for (auto& edge : edges) {
            if (!dsu.unionNodes(edge[0], edge[1])) {
                return false;
            }
        }
        return dsu.components() == 1;
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode Watch NeetCode on YouTube

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations