261. Graph Valid Tree

📝 Problem Details

• Title: 261. Graph Valid Tree
• Link: https://leetcode.com/problems/graph-valid-tree/
• Difficulty: Medium
• Tags/Categories: Graphs DFS Trees

graph of n nodes labeled from 0 ~ n-1 input integer n input array edges where edges[i] = [ai,bi] indicating an undirected edge between the two nodes return true if the edges of the given graph make up a valid tree

💭What Were My Initial Thoughts?

- what makes a valid tree?

- a graph is a tree if and only if :
	- if contains exactly n-1 edges for n nodes
	- a tree always has n-1 edges (otherwise, it's either disconnected or contains cycles)

- a graph is fully connected 
	- every node must be reachable from a single root node 

- if the graph has more than n-1 edges, it contains a cycle
- if the graph has fewer than n-1 edges, its disconnected
- if exactly n-1 edges, we must still verify that all nodes are connected 

💡 Explanation of Solution

- build an adjacency list
	- since the input is an undirected graph, stores edges both ways in an adjacency list

- use dfs to detect cycles
	- track visited nodes using a visited array
	- base case for cycle detection:
		- if a node is revisited except through its parent, then a cycle exists

- ensure all nodes are connected
	- if DFS completes and some nodes remain unvisited, the graph is disconnected
	- we ensure connectivity by checking if all nodes were marked as visited

⌛ Complexity Analysis

Time Complexity: O(V+E)
Space Complexity: O(V+E)

💻 Implementation of Solution

class Solution {
public:
    bool validTree(int n, vector<vector<int>>& edges) {
        if (edges.size() != n - 1) return false; // Quick check: A tree must have exactly n-1 edges
 
        // Construct adjacency list
        vector<vector<int>> adjList(n);
        for (const auto& edge : edges) {
            int node1 = edge[0], node2 = edge[1];
            adjList[node1].push_back(node2);
            adjList[node2].push_back(node1);
        }
 
        vector<int> visited(n, 0); // 0 = Unvisited, 1 = Visiting, 2 = Processed
 
        // Start DFS from node 0
        if (hasCycle(0, -1, adjList, visited)) return false;
 
        // Ensure all nodes are connected
        return count(visited.begin(), visited.end(), 2) == n;
    }
 
private:
    bool hasCycle(int node, int parent, vector<vector<int>>& adjList, vector<int>& visited) {
        visited[node] = 1; // Mark as visiting
 
        for (int neighbor : adjList[node]) {
            if (neighbor == parent) continue; // Ignore edge leading back to parent
            
            if (visited[neighbor] == 1) return true; // Cycle detected
            if (visited[neighbor] == 0 && hasCycle(neighbor, node, adjList, visited))
                return true; // Cycle found in DFS
 
        }
 
        visited[node] = 2; // Mark as processed
        return false;
    }
};