Course4all
Join us on telegram
Home/dsa/Graphs/Graph Valid Tree

Graph Valid Tree

Master this topic with zero to advance depth.

Graph Valid Tree

You have a graph of n nodes labeled from 0 to n - 1. You are given an array edges where edges[i] = [a_i, b_i] indicates that there is an undirected edge between nodes a_i and b_i in the graph.

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

Visual Representation

n=5, edges=[[0,1],[0,2],[0,3],[1,4]] 0 /|\n 1 2 3 | 4 Valid Tree! Result: true
Medium

Examples

Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
Output: true

All nodes are connected and there are no cycles.

Approach 1

Level I: Brute Force (DFS / BFS)

Intuition

A graph is a tree if it is connected and has no cycles. We can perform a traversal from any node and check:

  1. Did we visit all NN nodes?
  2. Did we encounter any already-visited nodes during traversal (cycle)?

Thought Process

  1. Build adjacency list.
  2. Start DFS from node 0.
  3. Keep track of visited nodes. For each neighbor, make sure it's not the immediate parent (to handle undirected edges).
  4. If a neighbor is already in visited, return False (cycle).
  5. After DFS, check if visited.size() == n.

Pattern: Cycle Detection in Undirected Graph

⏱ O(V + E) - Standard traversal.💾 O(V + E) - Adjacency list and visited set.

Detailed Dry Run

n=3, edges=[[0,1],[1,2],[2,0]]

  • DFS(0): mark 0 visited, neighbor 1.
  • DFS(1): mark 1 visited, neighbor 0 (skip), neighbor 2.
  • DFS(2): mark 2 visited, neighbor 1 (skip), neighbor 0 (ALREADY VISITED!) -> Cycle found, return False.
java
class Solution {
    public boolean validTree(int n, int[][] edges) {
        if (edges.length != n - 1) return false;
        List<Integer>[] adj = new List[n];
        for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
        for (int[] e : edges) { adj[e[0]].add(e[1]); adj[e[1]].add(e[0]); }
        Set<Integer> visited = new HashSet<>();
        if (!dfs(0, -1, adj, visited)) return false;
        return visited.size() == n;
    }
    private boolean dfs(int u, int p, List<Integer>[] adj, Set<Integer> vis) {
        if (vis.contains(u)) return false;
        vis.add(u);
        for (int v : adj[u]) {
            if (v == p) continue;
            if (!dfs(v, u, adj, vis)) return false;
        }
        return true;
    }
}
Approach 2

Level III: Optimal (Union-Find)

Intuition

This is the most efficient way to check for both conditions. As we add edges, if two nodes already have the same root, adding an edge between them creates a cycle. Connectivity is guaranteed if we process exactly N−1N-1 edges without cycles.

Thought Process

  1. Fundamental Tree Property: A valid tree with NN nodes MUST have exactly N−1N-1 edges. If len(edges) != n - 1, return False.
  2. Use Union-Find (DSU) with Path Compression.
  3. For each edge (u, v):
    • Find roots of u and v.
    • If roots are the same, return False (cycle detected).
    • Otherwise, union them.
  4. If all edges processed, return True.

Pattern: Disjoint Set Union (DSU)

⏱ O(E * alpha(N)) - Where alpha is the inverse Ackermann function (nearly constant).💾 O(V) - For the parent/rank arrays.

Detailed Dry Run

n=4, edges=[[0,1],[1,2],[2,3]]

  1. Edge (0,1): Union(0,1). Roots: 0,1. OK.
  2. Edge (1,2): Union(1,2). Roots: 0,2. OK.
  3. Edge (2,3): Union(2,3). Roots: 0,3. OK. All connected, no cycles. True.
java
class Solution {
    public boolean validTree(int n, int[][] edges) {
        if (edges.length != n - 1) return false;
        int[] parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
        for (int[] e : edges) {
            int root1 = find(parent, e[0]), root2 = find(parent, e[1]);
            if (root1 == root2) return false;
            parent[root1] = root2;
        }
        return true;
    }
    private int find(int[] parent, int i) {
        if (parent[i] == i) return i;
        return parent[i] = find(parent, parent[i]);
    }
}
← Previous QuestionCourse Schedule II
Next Question →Minimum Height Trees