Graph Valid Tree

🎯

Graph Valid Tree

mediumGRAPHGoogleLinkedInFacebook

Imagine you are designing a network of computers and want to ensure the network forms a valid tree structure without any cycles or disconnected parts.

💡 This problem tests your understanding of graph connectivity and cycle detection. Beginners often struggle because they confuse trees with general graphs and overlook the importance of both connectivity and absence of cycles.

📋

Problem Statement

Given n nodes labeled from 0 to n-1 and a list of undirected edges (each edge is a pair of nodes), determine if these edges make up a valid tree. A valid tree is a connected graph with no cycles.

1 ≤ n ≤ 10^5edges.length == n - 10 ≤ edges[i][0], edges[i][1] < nNo duplicate edgesNo self-loops

💡

Example

Input"n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]"

Outputtrue

The graph is connected and has no cycles, so it forms a valid tree.

Input"n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]"

Outputfalse

The graph contains a cycle (1-2-3-1), so it is not a valid tree.

• n = 1, edges = [] → true (single node is a valid tree)
• n = 2, edges = [] → false (disconnected nodes)
• n = 4, edges = [[0,1],[2,3]] → false (two disconnected components)
• n = 3, edges = [[0,1],[1,2],[2,0]] → false (cycle present)

⚠️

Common Mistakes

Not checking if all nodes are visited after DFS

Returns true even if graph is disconnected

✅ Verify visited set size equals n after traversal

Detecting cycle without considering parent node in DFS

False positive cycle detection due to back edge to parent

✅ Pass parent node in DFS and skip it when checking neighbors

Not checking edge count equals n-1 before processing

Wastes time on impossible cases, may miss invalid trees

✅ Return false immediately if edges length != n-1

Using recursion without limiting stack depth for large n

Stack overflow or runtime error on large inputs

✅ Use iterative BFS or increase recursion limit if allowed

Union-Find without path compression or rank optimization

Slower performance on large inputs

✅ Implement path compression and union by rank

🧠

Brute Force (DFS Cycle Detection + Connectivity Check)

💡 Starting with brute force helps understand the fundamental graph properties: connectivity and cycle detection. It uses basic DFS traversal without optimizations.

Intuition

If the graph is connected and has no cycles, it is a valid tree. We can check connectivity by DFS from node 0 and detect cycles by tracking visited nodes and parent relationships.

Algorithm

1. Build adjacency list from edges.
2. Initialize a visited set to track visited nodes.
3. Perform DFS from node 0, passing parent node to detect cycles.
4. If a cycle is detected during DFS, return false.
5. After DFS, check if all nodes are visited to ensure connectivity.
6. Return true if no cycles and graph is connected.

💡 The challenge is to detect cycles correctly by remembering the parent node to avoid false positives and ensuring all nodes are visited.

</>

Code

from collections import defaultdict

def valid_tree(n, edges):
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    visited = set()

    def dfs(node, parent):
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor == parent:
                continue
            if neighbor in visited or not dfs(neighbor, node):
                return False
        return True

    if not dfs(0, -1):
        return False
    return len(visited) == n

# Driver code
if __name__ == '__main__':
    print(valid_tree(5, [[0,1],[0,2],[0,3],[1,4]]))  # True
    print(valid_tree(5, [[0,1],[1,2],[2,3],[1,3],[1,4]]))  # False

Line Notes

graph = defaultdict(list)Build adjacency list for efficient neighbor lookup

for u, v in edgesAdd edges bidirectionally since graph is undirected

visited = set()Track nodes visited during DFS to detect cycles and connectivity

def dfs(node, parent)DFS function with parent to avoid false cycle detection

if neighbor == parentSkip the edge leading back to parent node

if neighbor in visited or not dfs(neighbor, node)Detect cycle if neighbor already visited or DFS fails

if not dfs(0, -1)Start DFS from node 0, no parent (-1)

return len(visited) == nCheck if all nodes are visited to confirm connectivity

import java.util.*;

public class Solution {
    public boolean validTree(int n, int[][] edges) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }
        boolean[] visited = new boolean[n];
        if (!dfs(0, -1, graph, visited)) return false;
        for (boolean v : visited) if (!v) return false;
        return true;
    }

    private boolean dfs(int node, int parent, List<List<Integer>> graph, boolean[] visited) {
        visited[node] = true;
        for (int neighbor : graph.get(node)) {
            if (neighbor == parent) continue;
            if (visited[neighbor] || !dfs(neighbor, node, graph, visited)) return false;
        }
        return true;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.validTree(5, new int[][]{{0,1},{0,2},{0,3},{1,4}})); // true
        System.out.println(sol.validTree(5, new int[][]{{0,1},{1,2},{2,3},{1,3},{1,4}})); // false
    }
}

Line Notes

List<List<Integer>> graph = new ArrayList<>()Initialize adjacency list for graph representation

for (int[] edge : edges)Add edges bidirectionally for undirected graph

boolean[] visited = new boolean[n]Track visited nodes during DFS

if (!dfs(0, -1, graph, visited))Start DFS from node 0 with no parent

if (neighbor == parent) continueAvoid revisiting the parent node to prevent false cycle detection

if (visited[neighbor] || !dfs(neighbor, node, graph, visited))Detect cycle if neighbor visited or DFS fails

for (boolean v : visited) if (!v) return falseCheck connectivity by ensuring all nodes visited

return trueReturn true if no cycles and graph is connected

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

class Solution {
public:
    bool validTree(int n, vector<vector<int>>& edges) {
        vector<vector<int>> graph(n);
        for (auto& edge : edges) {
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
        }
        vector<bool> visited(n, false);
        if (!dfs(0, -1, graph, visited)) return false;
        for (bool v : visited) if (!v) return false;
        return true;
    }

private:
    bool dfs(int node, int parent, vector<vector<int>>& graph, vector<bool>& visited) {
        visited[node] = true;
        for (int neighbor : graph[node]) {
            if (neighbor == parent) continue;
            if (visited[neighbor] || !dfs(neighbor, node, graph, visited)) return false;
        }
        return true;
    }
};

int main() {
    Solution sol;
    vector<vector<int>> edges1 = {{0,1},{0,2},{0,3},{1,4}};
    cout << boolalpha << sol.validTree(5, edges1) << endl; // true
    vector<vector<int>> edges2 = {{0,1},{1,2},{2,3},{1,3},{1,4}};
    cout << boolalpha << sol.validTree(5, edges2) << endl; // false
    return 0;
}

Line Notes

vector<vector<int>> graph(n)Create adjacency list for graph

for (auto& edge : edges)Add edges bidirectionally for undirected graph

vector<bool> visited(n, false)Track visited nodes during DFS

if (!dfs(0, -1, graph, visited))Start DFS from node 0 with no parent

if (neighbor == parent) continueSkip parent node to avoid false cycle detection

if (visited[neighbor] || !dfs(neighbor, node, graph, visited))Detect cycle if neighbor visited or DFS fails

for (bool v : visited) if (!v) return falseCheck if all nodes visited to confirm connectivity

return trueReturn true if graph is connected and acyclic

function validTree(n, edges) {
    const graph = new Array(n).fill(0).map(() => []);
    for (const [u, v] of edges) {
        graph[u].push(v);
        graph[v].push(u);
    }
    const visited = new Set();
    function dfs(node, parent) {
        visited.add(node);
        for (const neighbor of graph[node]) {
            if (neighbor === parent) continue;
            if (visited.has(neighbor) || !dfs(neighbor, node)) return false;
        }
        return true;
    }
    if (!dfs(0, -1)) return false;
    return visited.size === n;
}

// Test cases
console.log(validTree(5, [[0,1],[0,2],[0,3],[1,4]])); // true
console.log(validTree(5, [[0,1],[1,2],[2,3],[1,3],[1,4]])); // false

Line Notes

const graph = new Array(n).fill(0).map(() => [])Initialize adjacency list for graph

for (const [u, v] of edges)Add edges bidirectionally for undirected graph

const visited = new Set()Track visited nodes during DFS

function dfs(node, parent)DFS function with parent to detect cycles

if (neighbor === parent) continueSkip edge back to parent to avoid false cycle detection

if (visited.has(neighbor) || !dfs(neighbor, node))Detect cycle if neighbor visited or DFS fails

if (!dfs(0, -1)) return falseStart DFS from node 0 with no parent

return visited.size === nCheck if all nodes are visited to confirm connectivity

⏱

Complexity

TimeO(n)

SpaceO(n)

Building adjacency list takes O(n). DFS visits each node and edge once, total O(n). Visited set and recursion stack use O(n) space.

💡 For n=1000, this means roughly 1000 operations, which is efficient enough for interviews.

Interview Verdict: Accepted

This approach is simple and efficient enough for the problem constraints, making it a solid baseline solution.

🧠

Union-Find (Disjoint Set) for Cycle Detection and Connectivity

💡 Union-Find is a classic data structure that efficiently detects cycles and checks connectivity by grouping nodes into sets. It avoids explicit graph traversal.

Intuition

If adding an edge connects two nodes already in the same set, a cycle exists. After processing all edges, if there is exactly one connected component, the graph is a valid tree.

Algorithm

1. Initialize parent array where each node is its own parent.
2. Define find function to get root parent with path compression.
3. Define union function to merge two sets; if roots are same, cycle detected.
4. For each edge, perform union; if union fails, return false.
5. After processing all edges, check if number of edges is n-1 to ensure connectivity.
6. Return true if no cycles and edges count is n-1.

💡 Union-Find abstracts cycle detection and connectivity into simple union and find operations, making the code concise and efficient.

</>

Code

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0]*n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX == rootY:
            return False
        if self.rank[rootX] < self.rank[rootY]:
            self.parent[rootX] = rootY
        elif self.rank[rootX] > self.rank[rootY]:
            self.parent[rootY] = rootX
        else:
            self.parent[rootY] = rootX
            self.rank[rootX] += 1
        return True

def valid_tree(n, edges):
    if len(edges) != n - 1:
        return False
    uf = UnionFind(n)
    for u, v in edges:
        if not uf.union(u, v):
            return False
    return True

# Driver code
if __name__ == '__main__':
    print(valid_tree(5, [[0,1],[0,2],[0,3],[1,4]]))  # True
    print(valid_tree(5, [[0,1],[1,2],[2,3],[1,3],[1,4]]))  # False

Line Notes

self.parent = list(range(n))Initialize each node as its own parent

def find(self, x)Find root parent with path compression for efficiency

if rootX == rootYIf both nodes share root, cycle detected

if len(edges) != n - 1Quick check: valid tree must have exactly n-1 edges

if not uf.union(u, v)If union fails, cycle exists

return TrueNo cycles and correct edge count means valid tree

public class Solution {
    class UnionFind {
        int[] parent, rank;
        public UnionFind(int n) {
            parent = new int[n];
            rank = new int[n];
            for (int i = 0; i < n; i++) parent[i] = i;
        }
        public int find(int x) {
            if (parent[x] != x) parent[x] = find(parent[x]);
            return parent[x];
        }
        public boolean union(int x, int y) {
            int rootX = find(x), rootY = find(y);
            if (rootX == rootY) return false;
            if (rank[rootX] < rank[rootY]) parent[rootX] = rootY;
            else if (rank[rootX] > rank[rootY]) parent[rootY] = rootX;
            else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
            return true;
        }
    }

    public boolean validTree(int n, int[][] edges) {
        if (edges.length != n - 1) return false;
        UnionFind uf = new UnionFind(n);
        for (int[] edge : edges) {
            if (!uf.union(edge[0], edge[1])) return false;
        }
        return true;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.validTree(5, new int[][]{{0,1},{0,2},{0,3},{1,4}})); // true
        System.out.println(sol.validTree(5, new int[][]{{0,1},{1,2},{2,3},{1,3},{1,4}})); // false
    }
}

Line Notes

parent = new int[n]Initialize each node as its own parent

if (parent[x] != x) parent[x] = find(parent[x])Path compression to flatten tree for efficiency

if (rootX == rootY) return falseCycle detected if both nodes share root

if (edges.length != n - 1) return falseQuick check for valid tree edge count

if (!uf.union(edge[0], edge[1])) return falseUnion fails means cycle detected

return trueNo cycles and correct edges means valid tree

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

class UnionFind {
    vector<int> parent, rank;
public:
    UnionFind(int n) : parent(n), rank(n, 0) {
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    bool unionSet(int x, int y) {
        int rootX = find(x), rootY = find(y);
        if (rootX == rootY) return false;
        if (rank[rootX] < rank[rootY]) parent[rootX] = rootY;
        else if (rank[rootX] > rank[rootY]) parent[rootY] = rootX;
        else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
        return true;
    }
};

class Solution {
public:
    bool validTree(int n, vector<vector<int>>& edges) {
        if (edges.size() != n - 1) return false;
        UnionFind uf(n);
        for (auto& edge : edges) {
            if (!uf.unionSet(edge[0], edge[1])) return false;
        }
        return true;
    }
};

int main() {
    Solution sol;
    vector<vector<int>> edges1 = {{0,1},{0,2},{0,3},{1,4}};
    cout << boolalpha << sol.validTree(5, edges1) << endl; // true
    vector<vector<int>> edges2 = {{0,1},{1,2},{2,3},{1,3},{1,4}};
    cout << boolalpha << sol.validTree(5, edges2) << endl; // false
    return 0;
}

Line Notes

vector<int> parent, rankParent and rank arrays for Union-Find structure

if (parent[x] != x) parent[x] = find(parent[x])Path compression for efficient find

if (rootX == rootY) return falseCycle detected if roots are same

if (edges.size() != n - 1) return falseCheck edge count for valid tree

if (!uf.unionSet(edge[0], edge[1])) return falseUnion fails means cycle detected

return trueNo cycles and correct edges means valid tree

class UnionFind {
    constructor(n) {
        this.parent = Array.from({length: n}, (_, i) => i);
        this.rank = new Array(n).fill(0);
    }
    find(x) {
        if (this.parent[x] !== x) {
            this.parent[x] = this.find(this.parent[x]);
        }
        return this.parent[x];
    }
    union(x, y) {
        const rootX = this.find(x);
        const rootY = this.find(y);
        if (rootX === rootY) return false;
        if (this.rank[rootX] < this.rank[rootY]) {
            this.parent[rootX] = rootY;
        } else if (this.rank[rootX] > this.rank[rootY]) {
            this.parent[rootY] = rootX;
        } else {
            this.parent[rootY] = rootX;
            this.rank[rootX]++;
        }
        return true;
    }
}

function validTree(n, edges) {
    if (edges.length !== n - 1) return false;
    const uf = new UnionFind(n);
    for (const [u, v] of edges) {
        if (!uf.union(u, v)) return false;
    }
    return true;
}

// Test cases
console.log(validTree(5, [[0,1],[0,2],[0,3],[1,4]])); // true
console.log(validTree(5, [[0,1],[1,2],[2,3],[1,3],[1,4]])); // false

Line Notes

this.parent = Array.from({length: n}, (_, i) => i)Initialize each node as its own parent

if (this.parent[x] !== x)Path compression to speed up find

if (rootX === rootY) return falseCycle detected if roots are same

if (edges.length !== n - 1) return falseCheck edge count for valid tree

if (!uf.union(u, v)) return falseUnion fails means cycle detected

return trueNo cycles and correct edges means valid tree

⏱

Complexity

TimeO(n α(n))

SpaceO(n)

Union-Find operations take near constant amortized time (α is inverse Ackermann function). Processing all edges is O(n).

💡 For n=1000, this is practically linear time, very efficient for large graphs.

Interview Verdict: Accepted

Union-Find is a preferred approach in interviews for its efficiency and clean cycle detection.

🧠

BFS for Connectivity and Cycle Detection

💡 BFS can also be used to detect cycles and check connectivity by level-order traversal, providing an alternative to DFS.

Intuition

Starting from node 0, BFS visits nodes layer by layer. If a visited node is encountered again from a different parent, a cycle exists. After BFS, if all nodes are visited, the graph is connected.

Algorithm

1. Build adjacency list from edges.
2. Initialize a queue and visited set.
3. Start BFS from node 0, enqueue it with parent -1.
4. For each dequeued node, check neighbors:
5. If neighbor not visited, enqueue with current node as parent.
6. If neighbor visited and not parent, cycle detected.
7. After BFS, check if all nodes visited for connectivity.
8. Return true if no cycles and graph is connected.

💡 BFS requires careful parent tracking to avoid false cycle detection and ensure all nodes are reached.

</>

Code

from collections import defaultdict, deque

def valid_tree(n, edges):
    if len(edges) != n - 1:
        return False
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    visited = set()
    queue = deque([(0, -1)])

    while queue:
        node, parent = queue.popleft()
        if node in visited:
            return False
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor == parent:
                continue
            if neighbor in visited:
                return False
            queue.append((neighbor, node))

    return len(visited) == n

# Driver code
if __name__ == '__main__':
    print(valid_tree(5, [[0,1],[0,2],[0,3],[1,4]]))  # True
    print(valid_tree(5, [[0,1],[1,2],[2,3],[1,3],[1,4]]))  # False

Line Notes

if len(edges) != n - 1Quick check for valid tree edge count

graph = defaultdict(list)Build adjacency list for graph

queue = deque([(0, -1)])Initialize BFS queue with node 0 and no parent

if node in visitedIf node already visited, cycle detected

if neighbor == parentSkip edge back to parent to avoid false cycle detection

if neighbor in visitedCycle detected if neighbor visited and not parent

queue.append((neighbor, node))Enqueue neighbor with current node as parent

return len(visited) == nCheck connectivity by ensuring all nodes visited

import java.util.*;

public class Solution {
    public boolean validTree(int n, int[][] edges) {
        if (edges.length != n - 1) return false;
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }
        boolean[] visited = new boolean[n];
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, -1});

        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int node = curr[0], parent = curr[1];
            if (visited[node]) return false;
            visited[node] = true;
            for (int neighbor : graph.get(node)) {
                if (neighbor == parent) continue;
                if (visited[neighbor]) return false;
                queue.offer(new int[]{neighbor, node});
            }
        }
        for (boolean v : visited) if (!v) return false;
        return true;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.validTree(5, new int[][]{{0,1},{0,2},{0,3},{1,4}})); // true
        System.out.println(sol.validTree(5, new int[][]{{0,1},{1,2},{2,3},{1,3},{1,4}})); // false
    }
}

Line Notes

if (edges.length != n - 1) return falseQuick check for valid tree edge count

List<List<Integer>> graph = new ArrayList<>()Build adjacency list

Queue<int[]> queue = new LinkedList<>()Initialize BFS queue

if (visited[node]) return falseCycle detected if node visited again

if (neighbor == parent) continueSkip edge back to parent

if (visited[neighbor]) return falseCycle detected if neighbor visited and not parent

queue.offer(new int[]{neighbor, node})Enqueue neighbor with current node as parent

for (boolean v : visited) if (!v) return falseCheck connectivity by ensuring all nodes visited

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

class Solution {
public:
    bool validTree(int n, vector<vector<int>>& edges) {
        if (edges.size() != n - 1) return false;
        vector<vector<int>> graph(n);
        for (auto& edge : edges) {
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
        }
        vector<bool> visited(n, false);
        queue<pair<int,int>> q;
        q.push({0, -1});

        while (!q.empty()) {
            auto [node, parent] = q.front(); q.pop();
            if (visited[node]) return false;
            visited[node] = true;
            for (int neighbor : graph[node]) {
                if (neighbor == parent) continue;
                if (visited[neighbor]) return false;
                q.push({neighbor, node});
            }
        }
        for (bool v : visited) if (!v) return false;
        return true;
    }
};

int main() {
    Solution sol;
    vector<vector<int>> edges1 = {{0,1},{0,2},{0,3},{1,4}};
    cout << boolalpha << sol.validTree(5, edges1) << endl; // true
    vector<vector<int>> edges2 = {{0,1},{1,2},{2,3},{1,3},{1,4}};
    cout << boolalpha << sol.validTree(5, edges2) << endl; // false
    return 0;
}

Line Notes

if (edges.size() != n - 1) return falseCheck edge count for valid tree

vector<vector<int>> graph(n)Build adjacency list

queue<pair<int,int>> qQueue stores node and its parent for BFS

if (visited[node]) return falseCycle detected if node visited again

if (neighbor == parent) continueSkip edge back to parent

if (visited[neighbor]) return falseCycle detected if neighbor visited and not parent

q.push({neighbor, node})Enqueue neighbor with current node as parent

for (bool v : visited) if (!v) return falseCheck connectivity by ensuring all nodes visited

function validTree(n, edges) {
    if (edges.length !== n - 1) return false;
    const graph = Array.from({length: n}, () => []);
    for (const [u, v] of edges) {
        graph[u].push(v);
        graph[v].push(u);
    }
    const visited = new Set();
    const queue = [[0, -1]];

    while (queue.length > 0) {
        const [node, parent] = queue.shift();
        if (visited.has(node)) return false;
        visited.add(node);
        for (const neighbor of graph[node]) {
            if (neighbor === parent) continue;
            if (visited.has(neighbor)) return false;
            queue.push([neighbor, node]);
        }
    }
    return visited.size === n;
}

// Test cases
console.log(validTree(5, [[0,1],[0,2],[0,3],[1,4]])); // true
console.log(validTree(5, [[0,1],[1,2],[2,3],[1,3],[1,4]])); // false

Line Notes

if (edges.length !== n - 1) return falseQuick check for valid tree edge count

const graph = Array.from({length: n}, () => [])Build adjacency list

const queue = [[0, -1]]Initialize BFS queue with node 0 and no parent

if (visited.has(node)) return falseCycle detected if node visited again

if (neighbor === parent) continueSkip edge back to parent

if (visited.has(neighbor)) return falseCycle detected if neighbor visited and not parent

queue.push([neighbor, node])Enqueue neighbor with current node as parent

return visited.size === nCheck connectivity by ensuring all nodes visited

⏱

Complexity

TimeO(n)

SpaceO(n)

Building adjacency list and BFS traversal each take O(n). Visited set and queue use O(n) space.

💡 For n=1000, BFS visits each node once, making it efficient for interview constraints.

Interview Verdict: Accepted

BFS is a good alternative to DFS, especially if you prefer iterative solutions.

📊

All Approaches - One-Glance Tradeoffs

💡 Union-Find is usually the best approach to code in interviews due to its efficiency and simplicity. DFS and BFS are good for understanding and alternative solutions.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (DFS)	O(n)	O(n)	Yes (deep recursion possible)	N/A	Good to explain graph properties; acceptable to code if comfortable with recursion
2. Union-Find	O(n α(n))	O(n)	No	N/A	Preferred approach for efficiency and clarity
3. BFS	O(n)	O(n)	No	N/A	Good iterative alternative to DFS

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice multiple approaches, and prepare to explain your reasoning clearly in interviews.

How to Present

Step 1: Clarify the problem and constraints, especially the meaning of a valid tree.Step 2: Present the brute force DFS approach to check connectivity and detect cycles.Step 3: Discuss the Union-Find approach as an efficient alternative.Step 4: Optionally mention BFS as another traversal method.Step 5: Code your chosen approach carefully, test with edge cases, and explain your complexity.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 10min → Test & Explain: 5min. Total ~20min

What the Interviewer Tests

The interviewer tests your understanding of graph connectivity, cycle detection, and ability to implement graph traversal or Union-Find correctly.

Common Follow-ups

• What if edges are not guaranteed to be n-1? → Check edge count first.
• Can you detect cycles in directed graphs? → Different approach needed (DFS with recursion stack).

💡 These follow-ups test your knowledge of graph properties beyond undirected trees.

🔍

Pattern Recognition

When to Use

1) Graph with n nodes and edges given; 2) Need to check if graph is a tree; 3) Check connectivity and cycles; 4) Edges count is n-1

Signature Phrases

valid treeno cyclesconnected graphn - 1 edges

NOT This Pattern When

Problems involving directed graphs or weighted edges require different techniques.

Similar Problems

Number of Connected Components in an Undirected Graph - focuses on connectivityRedundant Connection - detects cycles in undirected graphGraph Bipartite Check - uses BFS/DFS for graph property checks

Practice

1. You are given a town with n people labeled from 1 to n. Some people trust others, represented as pairs [a, b] meaning person a trusts person b. The town judge is defined as someone who trusts nobody but is trusted by everyone else. Which approach guarantees finding the town judge efficiently?

easy

A. Use a single array to track trust scores by incrementing for trusted and decrementing for trusting, then find the person with score n-1.

B. Use a brute force approach checking each person by scanning the entire trust list twice.

C. Use dynamic programming to build a trust matrix and find the person with the highest trust count.

D. Use a greedy approach to pick the person trusted by the most and verify if they trust nobody.

Solution

1. Step 1: Understand the problem constraints

   The town judge trusts nobody and is trusted by everyone else, so their trust score should be exactly n-1.

2. Step 2: Use a single trust score array

   Increment the score for each person trusted and decrement for each person who trusts someone else. The judge will have a score of n-1.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Single pass with trust score array finds judge efficiently [OK]

Hint: Trust score array captures trust relationships efficiently [OK]

Common Mistakes:

• Assuming greedy max trusted person is always judge
• Using DP unnecessarily
• Brute force is too slow for large inputs

2. You are given a directed graph with weighted edges representing travel times between nodes. Starting from a given node, you want to find the minimum time it takes for a signal to reach all other nodes. Which algorithmic approach guarantees finding the shortest travel times in this scenario?

easy

A. Use Dijkstra's algorithm with a priority queue to greedily select the next closest node.

B. Use a greedy algorithm that always picks the edge with the smallest weight regardless of path.

C. Use a simple Breadth-First Search (BFS) assuming all edges have equal weight.

D. Use a Depth-First Search (DFS) with path relaxation to explore all paths.

Solution

1. Step 1: Understand the problem requires shortest paths with weighted edges

   BFS assumes equal edge weights and cannot handle varying weights correctly, so it fails here.

2. Step 2: Identify that Dijkstra's algorithm uses a priority queue to always pick the next closest node, guaranteeing optimal shortest paths in graphs with non-negative weights

   DFS with path relaxation is inefficient and does not guarantee optimality without pruning, and greedy edge picking ignores path costs.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Dijkstra handles weighted shortest paths optimally [OK]

Hint: Dijkstra handles weighted shortest paths optimally [OK]

Common Mistakes:

• Assuming BFS works for weighted graphs
• Thinking DFS with relaxation is efficient
• Believing greedy edge picking always works

3. What is the time complexity of the optimal approach using a single trust score array to find the town judge, given n people and m trust pairs?

medium

A. O(n * m) because we scan trust pairs for each person

B. O(n^2) because we check trust relationships pairwise

C. O(m^2) because trust pairs are nested in loops

D. O(n + m) because we process each trust pair once and then scan all people once

Solution

1. Step 1: Identify loops in the algorithm

   The algorithm iterates once over all trust pairs (m) and then once over all people (n).

2. Step 2: Combine complexities

   Processing trust pairs is O(m), scanning people is O(n), total O(n + m).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Single pass over trust and people arrays [OK]

Hint: Single pass over trust pairs and people yields O(n + m) [OK]

Common Mistakes:

• Assuming nested loops cause O(n*m)
• Confusing trust pairs count with people count
• Ignoring linear scans after trust processing

4. What is the time complexity of the BFS-based algorithm to find the maximum area of an island in an m x n grid, where each cell is visited at most once?

medium

A. O((m * n)^2) -- BFS could revisit cells multiple times in worst case

B. O(m + n) -- because BFS visits each row and column once

C. O(m * n) -- each cell is visited once and neighbors checked constant times

D. O(m * n) plus extra O(m * n) space for the visited set

Solution

1. Step 1: Identify BFS visits each cell at most once

   Each cell is enqueued and dequeued once, so total operations proportional to number of cells.

2. Step 2: Each cell checks up to 4 neighbors in constant time

   Neighbor checks are constant per cell, so total is O(m*n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Linear in grid size, no repeated visits [OK]

Hint: Each cell visited once -> O(m*n) time [OK]

Common Mistakes:

• Assuming BFS revisits cells multiple times
• Confusing rows+cols with total cells
• Ignoring constant neighbor checks

5. Suppose the course prerequisites can include self-dependencies (a course requiring itself) and multiple edges between the same courses. Which modification to the Kahn's Algorithm is necessary to correctly detect cycles in this scenario?

hard

A. Ignore self-loops and treat multiple edges as one; no algorithm change needed.

B. Use DFS with coloring instead of Kahn's Algorithm because BFS cannot detect self-loops.

C. Modify in-degree initialization to count self-loops and multiple edges correctly.

D. Add a check to detect self-loops explicitly before running Kahn's Algorithm.

Solution

1. Step 1: Understand impact of self-loops and multiple edges

   Self-loops increase in-degree of a node, and multiple edges increase in-degree counts accordingly.

2. Step 2: Modify in-degree initialization to count all edges accurately

   Counting all edges including self-loops ensures Kahn's Algorithm correctly identifies cycles by never reducing in-degree to zero for cyclic nodes.

3. Step 3: Confirm no other algorithm change needed

   Algorithm logic remains the same; accurate in-degree counts handle these cases.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Proper in-degree counts detect cycles including self-loops [OK]

Hint: Count all edges correctly to detect cycles including self-loops [OK]

Common Mistakes:

• Ignoring self-loops leads to false positives
• Assuming BFS cannot detect self-loops
• Treating multiple edges as single edge incorrectly