Graph Valid Tree: connected and no cycle

• Tree identity – a graph on n nodes is a tree if and only if it has exactly n-1 edges and is connected.
• Edge count check – if edges != n-1, return false immediately; too few means disconnected, too many means a cycle.
• BFS/DFS approach – build an adjacency list, traverse from any node, and check that all n nodes are visited.
• Union-Find approach – union each edge's endpoints; if a union finds both already in the same set, a cycle exists.
• Complexity – both approaches run in near-linear time: O(V + E) for traversal, O(E * alpha(V)) for Union-Find.

What is the Graph Valid Tree problem?

You are given n nodes (labelled 0 to n-1) and a list of undirected edges. The task is to determine whether these edges form a valid tree. A valid tree means the graph is fully connected (every node is reachable from every other) and contains no cycle.

In banking, this validates that an approval hierarchy has exactly one path between any two positions and no circular approval loops.

Why is edge count plus connectivity sufficient?

The key mathematical fact is: a graph on n nodes is a tree if and only if it has exactly n-1 edges and is connected. With exactly n-1 edges, connectivity and acyclicity are equivalent. You do not need a separate cycle test.

• Fewer than n-1 edges: the graph cannot be connected.
• Exactly n-1 edges and connected: no cycle is possible (adding one edge would create a cycle).
• More than n-1 edges: at least one cycle must exist.

package com.bank.service;

import java.util.*;

public class HierarchyValidator {

    public static boolean isValidTree(int n, int[][] edges) {
        // Step 1: edge count check
        if (edges.length != n - 1) return false;

        // Step 2: build adjacency list
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] edge : edges) {
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
        }

        // Step 3: BFS from node 0
        boolean[] visited = new boolean[n];
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(0);
        visited[0] = true;
        int visitCount = 1;

        while (!queue.isEmpty()) {
            int node = queue.poll();
            for (int neighbour : adj.get(node)) {
                if (!visited[neighbour]) {
                    visited[neighbour] = true;
                    visitCount++;
                    queue.offer(neighbour);
                }
            }
        }
        return visitCount == n;
    }

    public static void main(String[] args) {
        int[][] edges = {{0, 1}, {0, 2}, {0, 3}, {1, 4}};
        System.out.println("Valid tree: " + isValidTree(5, edges));
    }
}

Valid tree: true

How does the Union-Find approach work?

Union-Find processes each edge by unioning its endpoints. If both endpoints are already in the same component, the edge would create a cycle, so return false. After processing all edges, check that there is exactly one component.

package com.bank.service;

public class HierarchyValidatorUF {

    private int[] parent, rank;

    public boolean isValidTree(int n, int[][] edges) {
        if (edges.length != n - 1) return false;

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

        for (int[] edge : edges) {
            if (!union(edge[0], edge[1])) return false; // cycle detected
        }
        return true; // n-1 edges, no cycle -> connected tree
    }

    private int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }

    private boolean union(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return false; // already connected -> cycle
        if (rank[px] < rank[py]) parent[px] = py;
        else if (rank[px] > rank[py]) parent[py] = px;
        else { parent[py] = px; rank[px]++; }
        return true;
    }
}

How is BFS different from Union-Find for this problem?

| Aspect | BFS/DFS Approach | Union-Find Approach |
|---|---|---|
| Detects cycles | Implicitly via edge count | Explicitly when union finds same root |
| Checks connectivity | By counting visited nodes | By counting components after all unions |
| Space | O(V + E) for adjacency list | O(V) for parent and rank arrays |
| Time | O(V + E) | O(E * alpha(V)) nearly O(E) |
| Code simplicity | Straightforward BFS/DFS | Requires Union-Find implementation |

What are the edge cases?

• n = 1, no edges – a single node with no edges is a valid tree.
• n = 0 – an empty graph is trivially a tree (or debatable depending on definition).
• Self-loops – an edge from a node to itself is a cycle; with n-1 edges the graph would also be disconnected.
• Duplicate edges – two edges between the same pair create a cycle; the edge count check catches this.
• Disconnected components – edges.length == n-1 but nodes are split into components; the connectivity check catches this.

// Edge case: single node
System.out.println(isValidTree(1, new int[][]{})); // true

// Edge case: two components
int[][] disconnected = {{0, 1}, {2, 3}};
System.out.println(isValidTree(4, disconnected)); // false (only 2 edges, need 3)

What are common mistakes?

The most common mistake is checking only the edge count without verifying connectivity.

// WRONG: only checking edge count
public static boolean isValidTreeWrong(int n, int[][] edges) {
    return edges.length == n - 1; // misses disconnected graphs with extra components
}
// Graph: 0-1, 2-3 has 2 edges for n=4, which is not n-1=3, so this works by accident.
// But consider 0-1-2, 3-4-3(cycle): 3 edges for n=5 is not n-1=4, also caught.
// The real danger is n=4, edges: {0,1},{1,2},{3,3} -> 3 edges = n-1, but node 3 is isolated

// CORRECT: edge count + connectivity
public static boolean isValidTreeCorrect(int n, int[][] edges) {
    if (edges.length != n - 1) return false;
    // Plus BFS/DFS to confirm all nodes reachable
}

What is the time and space complexity?

BFS/DFS runs in O(V + E) time and uses O(V + E) space for the adjacency list and visited array. Union-Find runs in O(E * alpha(V)) time, which is effectively O(E), and uses O(V) space. Both are near-linear and suitable for validating hierarchies with millions of employees.

What should a senior engineer know?

A senior engineer should be able to prove why edge count plus connectivity suffices. The proof: a connected graph on n nodes with n-1 edges is a tree because removing any edge from a tree disconnects it, so a tree has the minimum number of edges for connectivity, which is n-1. Therefore, any connected graph with exactly n-1 edges must be a tree.

They should also know that Union-Find with path compression and union by rank gives amortised nearly-constant time per operation, making it the preferred choice when edges arrive in a stream and you want to detect cycles incrementally.