Graph Valid Tree

A tree is a special shape. Everything is connected, and there are no loops anywhere. Graph Valid Tree asks you to check if a given graph fits that shape. This question rewards a clear definition of a tree, and it gives you one more chance to practice union-find.

🎯 The Problem

You answer one yes-or-no question: does this graph form a valid tree? Here are the rules.

• You get nodes labeled 0 to n - 1 and a list of edges.
• Each edge connects two nodes both ways, so the graph is undirected.
• A valid tree needs every node reachable from every other node.
• A valid tree has no cycles. A cycle is a loop that lets you return to a node by a different path.
• A handy shortcut: a tree with n nodes always has exactly n - 1 edges.

For example, with 5 nodes and edges [[0,1],[0,2],[0,3],[1,4]], everything is reachable and there is no loop. So this is a valid tree.

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

Explanation: All 5 nodes are connected and there is no cycle.

Here is the graph. It branches out from node 0 with no loops.

🐢 Approach 1: DFS Connectivity and Cycle Check (Alternative)

The idea in one line: walk the graph once, catch any cycle on the way, then check that every node was reached.

The idea:

• Depth-first search follows one path as deep as it goes before backing up.
• Build an adjacency list of neighbors.
• Start at node 0 and visit everything reachable.

How it works:

• Mark each node visited and remember the node you came from.
• If you reach a visited node that is not the one you came from, that is a cycle. Not a tree.
• After the walk, check whether every node was visited.
• If some node was never reached, the graph is split. Not connected. Not a tree.

Why it is weak:

• You must track the parent carefully or you flag a false cycle.
• It needs the full adjacency list plus a separate connectivity scan.

Here is the DFS tree-check code:

def valid_tree(n, edges):
    if len(edges) != n - 1:
        return False
    graph = [[] for _ in range(n)]
    for a, b in edges:
        graph[a].append(b); graph[b].append(a)
    seen = set()
    def dfs(node, parent):
        seen.add(node)
        for nei in graph[node]:
            if nei == parent: continue
            if nei in seen or not dfs(nei, node): return False
        return True
    return dfs(0, -1) and len(seen) == n

⚡ Approach 2: Union-Find (Best)

The idea in one line: check the edge count is n - 1, then union each edge and fail the moment two endpoints already share a group.

The idea:

• Union-find tracks which group each node is in and merges groups fast.
• It is also called a disjoint set, because the groups never overlap.
• Each node points to a parent. Following parents up leads to the root.
• Two nodes are in the same group when they share a root.

How it works:

• If the edge count is not n - 1, return false right away.
• Start with every node in its own group.
• Read each edge. Find the root of both nodes.
• If they already share a root, this edge closes a loop. Not a tree.
• Otherwise merge their groups and continue.
• find(x) walks up to the root. union(a, b) joins two groups.
• Path compression points nodes straight at the root.
• Union by rank attaches the shorter group under the taller one.

Why it is fast:

• With n - 1 edges and no cycle, the graph must be connected. No separate scan needed.
• Path compression and union by rank make each operation almost constant time.

Here is the decision flow for the optimal check.

Steps to Solve

1. If the number of edges is not n - 1, return false right away.
2. Create a parent array where every node is its own parent, and a rank array of zeros.
3. Write find(x) that walks up to the root and points each node along the way straight to the root.
4. Write union(a, b) that finds both roots and attaches the lower-rank root under the higher-rank one.
5. For each edge, find both roots. If they match, a cycle exists, so return false.
6. Otherwise union the two nodes. If every edge passed with no cycle, return true.

#include <stdio.h>

#define MAXN 1000

int parent[MAXN];
int rnk[MAXN];

int find(int x) {
    if (parent[x] != x) parent[x] = find(parent[x]); // path compression
    return parent[x];
}

int unite(int a, int b) {
    int ra = find(a), rb = find(b);
    if (ra == rb) return 0;            // already connected, a cycle
    if (rnk[ra] < rnk[rb]) parent[ra] = rb;          // union by rank
    else if (rnk[ra] > rnk[rb]) parent[rb] = ra;
    else { parent[rb] = ra; rnk[ra]++; }
    return 1;
}

int validTree(int n, int edges[][2], int m) {
    if (m != n - 1) return 0;          // wrong edge count
    for (int i = 0; i < n; i++) { parent[i] = i; rnk[i] = 0; }
    for (int i = 0; i < m; i++) {
        if (!unite(edges[i][0], edges[i][1])) return 0; // cycle found
    }
    return 1;
}

int main(void) {
    int edges[][2] = {{0, 1}, {0, 2}, {0, 3}, {1, 4}};
    int ok = validTree(5, edges, 4);
    printf("%s\n", ok ? "true" : "false");
    return 0;
}

true

#include <iostream>
#include <vector>
using namespace std;

vector<int> parent, rnk;

int find(int x) {
    if (parent[x] != x) parent[x] = find(parent[x]); // path compression
    return parent[x];
}

bool unite(int a, int b) {
    int ra = find(a), rb = find(b);
    if (ra == rb) return false;        // already connected, a cycle
    if (rnk[ra] < rnk[rb]) parent[ra] = rb;          // union by rank
    else if (rnk[ra] > rnk[rb]) parent[rb] = ra;
    else { parent[rb] = ra; rnk[ra]++; }
    return true;
}

bool validTree(int n, vector<vector<int>>& edges) {
    if ((int)edges.size() != n - 1) return false;    // wrong edge count
    parent.assign(n, 0);
    rnk.assign(n, 0);
    for (int i = 0; i < n; i++) parent[i] = i;

    for (auto& e : edges) {
        if (!unite(e[0], e[1])) return false;        // cycle found
    }
    return true;
}

int main() {
    vector<vector<int>> edges = {{0, 1}, {0, 2}, {0, 3}, {1, 4}};
    cout << (validTree(5, edges) ? "true" : "false") << endl;
    return 0;
}

true

public class GraphValidTree {
    static int[] parent;
    static int[] rank;

    static int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]]; // path compression by halving
            x = parent[x];
        }
        return x;
    }

    static boolean union(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;        // already connected, a cycle
        if (rank[ra] < rank[rb]) parent[ra] = rb;        // union by rank
        else if (rank[ra] > rank[rb]) parent[rb] = ra;
        else { parent[rb] = ra; rank[ra]++; }
        return true;
    }

    public static boolean validTree(int n, int[][] edges) {
        if (edges.length != n - 1) return false;     // wrong edge count
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;

        for (int[] e : edges) {
            if (!union(e[0], e[1])) return false;     // cycle found
        }
        return true;
    }

    public static void main(String[] args) {
        int[][] edges = {{0, 1}, {0, 2}, {0, 3}, {1, 4}};
        System.out.println(validTree(5, edges));
    }
}

true

def valid_tree(n, edges):
    if len(edges) != n - 1:        # a tree has exactly n - 1 edges
        return False

    parent = list(range(n))        # each node is its own parent
    rank = [0] * n                 # rough height of each group

    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])  # path compression
        return parent[x]

    def union(a, b):
        ra, rb = find(a), find(b)
        if ra == rb:
            return False                 # already connected, a cycle
        if rank[ra] < rank[rb]:          # union by rank
            parent[ra] = rb
        elif rank[ra] > rank[rb]:
            parent[rb] = ra
        else:
            parent[rb] = ra
            rank[ra] += 1
        return True

    for a, b in edges:
        if not union(a, b):              # this edge closes a cycle
            return False
    return True


n = 5
edges = [[0, 1], [0, 2], [0, 3], [1, 4]]
print(valid_tree(n, edges))

True

function validTree(n, edges) {
  if (edges.length !== n - 1) return false; // a tree has n - 1 edges

  const parent = Array.from({ length: n }, (_, i) => i); // self parent
  const rank = new Array(n).fill(0);

  function find(x) {
    if (parent[x] !== x) parent[x] = find(parent[x]); // path compression
    return parent[x];
  }

  function union(a, b) {
    const ra = find(a);
    const rb = find(b);
    if (ra === rb) return false;        // already connected, a cycle
    if (rank[ra] < rank[rb]) parent[ra] = rb;        // union by rank
    else if (rank[ra] > rank[rb]) parent[rb] = ra;
    else { parent[rb] = ra; rank[ra]++; }
    return true;
  }

  for (const [a, b] of edges) {
    if (!union(a, b)) return false;     // this edge closes a cycle
  }
  return true;
}

const n = 5;
const edges = [[0, 1], [0, 2], [0, 3], [1, 4]];
console.log(validTree(n, edges));

true

Let us walk through the Python version line by line, because it combines two checks into one clean pass.

if len(edges) != n - 1: return False is the early exit. A tree with n nodes always has exactly n - 1 edges. Too few edges means the graph is split. Too many means a loop is guaranteed. Either way it is not a tree, so we stop here.

parent = list(range(n)) makes each node its own parent at first. rank = [0] * n starts every group with rank zero.

Inside find(x), the check if parent[x] != x: asks whether x is the root, the only node that points to itself. If not, parent[x] = find(parent[x]) finds the real root and points x straight at it. That is path compression.

Inside union(a, b), we get both roots. if ra == rb: return False is the cycle test. If the two nodes already share a root, joining them again would form a loop, so this is not a tree. The rank lines attach the shorter group under the taller one and only bump rank when the heights tie.

The loop reads each edge. if not union(a, b): return False stops the moment any edge would close a cycle. If every edge merged two separate groups, then with exactly n - 1 edges and no cycle, the graph must be fully connected. So we return True.

⏱️ Time and Space Complexity

The DFS approach builds an adjacency list and walks every node and edge once. So it is O(V + E) time and O(V + E) space. Union-find skips the adjacency list. The edge-count check is instant. With path compression and union by rank, each operation is almost constant time, the inverse Ackermann alpha of n, which stays tiny. So union-find runs in about O(E * alpha(V)) time and O(V) space. Both work well. Union-find is shorter to write and lighter on memory.

🧩 Key Takeaways

• ✅ A valid tree is fully connected and has no cycles.
• ✅ A tree with n nodes always has exactly n - 1 edges. Check this first.
• ✅ Union-find flags a cycle the moment an edge joins two nodes that already share a root.
• ✅ With n - 1 edges and no cycle, the graph is guaranteed connected.
• ✅ Path compression and union by rank keep each operation almost constant time.

🚀 What’s Next?

• Redundant Connection
• Course Schedule II