DSA 450 Notes

Problem Statement

Given an undirected graph with V vertices and E edges, check if it forms a valid tree. A graph is a tree if:

It is connected (all vertices are reachable from any vertex)
It has no cycles
It has exactly V-1 edges

Example 1:

Vertices: 5
Edges: [[0,1], [0,2], [0,3], [1,4]]

    0
   /|\
  1 2 3
  |
  4

Output: true (Connected, no cycles, 4 edges = 5-1)

Example 2:

Vertices: 5
Edges: [[0,1], [1,2], [2,3], [1,3], [1,4]]

Output: false (Has cycle: 1-2-3-1)

Approach 1: DFS - Check Connectivity and Cycles

Intuition

Use DFS to traverse the graph. Mark nodes as visited. If we encounter an already visited node (that's not the parent), there's a cycle. After DFS, check if all nodes are visited (connected).

Algorithm

Build adjacency list from edges
Check if number of edges = V-1 (quick check)
Run DFS from node 0, tracking visited nodes and parent
If we revisit a non-parent node, cycle exists → not a tree
After DFS, if all nodes visited and no cycle → it's a tree

java

import java.util.*;

public class Solution {
    private boolean hasCycleDFS(int node, int parent, List<List<Integer>> adj,
                                 boolean[] visited) {
        visited[node] = true;
        
        for (int neighbor : adj.get(node)) {
            if (!visited[neighbor]) {
                if (hasCycleDFS(neighbor, node, adj, visited)) {
                    return true;
                }
            } else if (neighbor != parent) {
                // Visited node that's not parent - cycle found
                return true;
            }
        }
        
        return false;
    }
    
    public boolean isTree(int n, int[][] edges) {
        // Quick check: tree must have exactly n-1 edges
        if (edges.length != n - 1) return false;
        
        // 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]);
        }
        
        // Check for cycles using DFS
        boolean[] visited = new boolean[n];
        if (hasCycleDFS(0, -1, adj, visited)) {
            return false;
        }
        
        // Check if all nodes are visited (connected)
        for (int i = 0; i < n; i++) {
            if (!visited[i]) return false;
        }
        
        return true;
    }
}

Complexity Analysis

Time Complexity: O(V + E) - DFS visits each vertex and edge once
Space Complexity: O(V + E) - Adjacency list + visited array + recursion stack

Approach 2: Optimal (Union-Find / Disjoint Set Union)

Intuition

Use Union-Find data structure. Process each edge and union the two vertices. If they're already in the same set, adding this edge creates a cycle. Finally, check if all vertices belong to the same set (connected).

Algorithm

Quick check: must have exactly V-1 edges
Initialize Union-Find with each node as its own parent
For each edge, try to union the two endpoints
If they already have the same root, cycle exists → not a tree
After all edges, check if only one connected component

java

import java.util.*;

class UnionFind {
    int[] parent, rank;
    int components;
    
    UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        components = n;
        
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }
    
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // Path compression
        }
        return parent[x];
    }
    
    boolean unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        
        if (rootX == rootY) {
            return false; // Already connected - cycle
        }
        
        // Union by rank
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
        
        components--;
        return true;
    }
    
    boolean isConnected() {
        return components == 1;
    }
}

public class Solution {
    public boolean isTree(int n, int[][] edges) {
        // Quick check: tree must have exactly n-1 edges
        if (edges.length != n - 1) return false;
        
        UnionFind uf = new UnionFind(n);
        
        for (int[] edge : edges) {
            // If union fails, cycle exists
            if (!uf.unite(edge[0], edge[1])) {
                return false;
            }
        }
        
        // Check if all nodes are connected
        return uf.isConnected();
    }
}

Complexity Analysis

Time Complexity: O(V + E × α(V)) ≈ O(V + E) - α is inverse Ackermann function, nearly constant
Space Complexity: O(V) - Only parent and rank arrays

Key Takeaways

Tree properties: Connected + No cycles + Exactly V-1 edges
Quick check: If edges ≠ V-1, immediately return false
DFS approach: Good for understanding, checks connectivity and cycles together
Union-Find approach: More efficient, especially for dynamic graph problems
Cycle detection in undirected graph: Track parent to avoid false positive from same edge

Check if given graph is tree or not [IMP]

Problem Statement

Approach 1: DFS - Check Connectivity and Cycles

Intuition

Algorithm

Complexity Analysis

Approach 2: Optimal (Union-Find / Disjoint Set Union)

Intuition

Algorithm

Complexity Analysis

Key Takeaways