Graph Valid Tree

📋

Problem

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.

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

Edge cases: 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)

</>

IDE

def valid_tree(n: int, edges: list[list[int]]) -> bool:public boolean validTree(int n, int[][] edges)bool validTree(int n, vector<vector<int>>& edges)function validTree(n, edges)

def valid_tree(n, edges):
    # Write your solution here
    pass

class Solution {
    public boolean validTree(int n, int[][] edges) {
        // Write your solution here
        return false;
    }
}

#include <vector>
using namespace std;

bool validTree(int n, vector<vector<int>>& edges) {
    // Write your solution here
    return false;
}

function validTree(n, edges) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: trueCycle detection logic misses back edges due to not tracking parent node properly.✅ In DFS, skip the parent node when checking neighbors to avoid false cycle detection.

Wrong: trueConnectivity check missing or incomplete; code returns true without verifying all nodes visited.✅ After DFS/BFS, verify visited nodes count equals n before returning true.

Wrong: falseIncorrect base case handling for single node graph with no edges.✅ Return true immediately if n=1 and edges is empty.

Wrong: falseOff-by-one error in DFS traversal causing premature cycle detection or missed nodes.✅ Ensure DFS correctly tracks parent and visits all nodes without false positives.

Wrong: TLEUsing exponential or quadratic algorithm instead of linear DFS or Union-Find.✅ Implement DFS or Union-Find with O(n) complexity for cycle detection and connectivity.

✓

Test Cases

Focus on handling minimal and boundary cases like single node or disconnected graphs.

Test your cycle detection carefully; watch for subtle cycles and parent tracking errors.

Optimize your solution to linear time using DFS or Union-Find to handle large inputs.

t1_01basic

Input{"n":5,"edges":[[0,1],[0,2],[0,3],[1,4]]}

Expectedtrue

⏱ Performance - must finish in 2000ms

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

💡 Check if the graph is connected and has no cycles.

💡 Use DFS or BFS to detect cycles and verify connectivity.

💡 Ensure all nodes are visited exactly once and no back edges exist.

Why it failed: Returned false but graph is connected and acyclic. Fix DFS to correctly track visited nodes and parent to avoid false cycle detection.

✓ Correctly identified a valid tree with no cycles and full connectivity.

t1_02basic

Input{"n":5,"edges":[[0,1],[1,2],[2,3],[1,3],[1,4]]}

Expectedfalse

⏱ Performance - must finish in 2000ms

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

💡 Look for cycles in the graph using DFS or Union-Find.

💡 Detect if any node is revisited during traversal except the parent.

💡 Return false if a cycle is detected even if graph is connected.

Why it failed: Returned true despite presence of cycle. Fix cycle detection logic to return false when a back edge is found.

✓ Correctly detected cycle and returned false.

t2_01edge

Input{"n":1,"edges":[]}

Expectedtrue

⏱ Performance - must finish in 2000ms

Single node with no edges is trivially a valid tree.

💡 Consider the base case of a single node graph.

💡 Check if the code handles n=1 and empty edges correctly.

💡 Return true if n=1 and no edges exist.

Why it failed: Returned false for single node with no edges. Fix base case to return true when n=1 and edges are empty.

✓ Correctly handled single node graph as valid tree.

t2_02edge

Input{"n":2,"edges":[]}

Expectedfalse

⏱ Performance - must finish in 2000ms

Two nodes with no edges are disconnected, so not a valid tree.

💡 Check if all nodes are reachable from the starting node.

💡 Verify connectivity by counting visited nodes after traversal.

💡 Return false if visited nodes count is less than n.

Why it failed: Returned true despite disconnected nodes. Fix connectivity check to ensure all nodes are visited.

✓ Correctly identified disconnected graph as invalid tree.

t2_03edge

Input{"n":4,"edges":[[0,1],[2,3]]}

Expectedfalse

⏱ Performance - must finish in 2000ms

Graph has two disconnected components, so it is not a valid tree.

💡 Check if graph is fully connected by verifying visited nodes count.

💡 Use DFS/BFS starting from node 0 and count visited nodes.

💡 Return false if visited nodes count is less than n.

Why it failed: Returned true despite disconnected components. Fix connectivity check to verify all nodes are visited.

✓ Correctly detected disconnected components and returned false.

t3_01corner

Input{"n":3,"edges":[[0,1],[1,2],[2,0]]}

Expectedfalse

⏱ Performance - must finish in 2000ms

Graph contains a cycle involving all nodes, so not a valid tree.

💡 Detect cycles by checking if a visited node is encountered again not via parent.

💡 Use DFS with parent tracking to avoid false positives.

💡 Return false immediately upon detecting a cycle.

Why it failed: Returned true despite cycle present. Fix DFS to track parent node and detect back edges properly.

✓ Correctly detected cycle and returned false.

t3_02corner

Input{"n":4,"edges":[[0,1],[1,2],[2,3]]}

Expectedtrue

⏱ Performance - must finish in 2000ms

Linear chain of nodes with no cycles is a valid tree.

💡 Check connectivity and absence of cycles in a chain graph.

💡 Ensure DFS visits all nodes and no back edges found.

💡 Return true if all nodes visited and no cycles detected.

Why it failed: Returned false incorrectly due to off-by-one or incorrect parent handling. Fix DFS to correctly handle linear chains.

✓ Correctly identified linear chain as valid tree.

t3_03corner

Input{"n":4,"edges":[[0,1],[1,2],[2,3],[3,1]]}

Expectedfalse

⏱ Performance - must finish in 2000ms

Graph has a cycle formed by edges 1-2-3-1, invalid tree.

💡 Detect cycles even if they are not immediately obvious.

💡 Use parent tracking in DFS to avoid mistaking parent edge as cycle.

💡 Return false on detecting any back edge.

Why it failed: Returned true despite cycle. Fix cycle detection to correctly identify back edges excluding parent.

✓ Correctly detected cycle and returned false.

t4_01performance

Input{"n":100,"edges":[[0,1],[1,2],[2,3],[3,4],[4,5],[5,6],[6,7],[7,8],[8,9],[9,10],[10,11],[11,12],[12,13],[13,14],[14,15],[15,16],[16,17],[17,18],[18,19],[19,20],[20,21],[21,22],[22,23],[23,24],[24,25],[25,26],[26,27],[27,28],[28,29],[29,30],[30,31],[31,32],[32,33],[33,34],[34,35],[35,36],[36,37],[37,38],[38,39],[39,40],[40,41],[41,42],[42,43],[43,44],[44,45],[45,46],[46,47],[47,48],[48,49],[49,50],[50,51],[51,52],[52,53],[53,54],[54,55],[55,56],[56,57],[57,58],[58,59],[59,60],[60,61],[61,62],[62,63],[63,64],[64,65],[65,66],[66,67],[67,68],[68,69],[69,70],[70,71],[71,72],[72,73],[73,74],[74,75],[75,76],[76,77],[77,78],[78,79],[79,80],[80,81],[81,82],[82,83],[83,84],[84,85],[85,86],[86,87],[87,88],[88,89],[89,90],[90,91],[91,92],[92,93],[93,94],[94,95],[95,96],[96,97],[97,98],[98,99]]}

Expectednull

⏱ Performance - must finish in 2000ms

n=100, edges form a linear chain (valid tree). Algorithm must run in O(n) time within 2 seconds.

💡 Use DFS or Union-Find for O(n) cycle detection and connectivity check.

💡 Avoid exponential or quadratic algorithms that will time out.

💡 Efficient adjacency list and visited tracking are key.

Why it failed: Solution timed out due to exponential or quadratic complexity. Optimize to O(n) DFS or Union-Find approach.

✓ Algorithm runs efficiently in O(n) time for large input.

Practice

1. Consider the following BFS-based cloneGraph function. Given the input graph with nodes 1 connected to 2 and 3, and node 2 connected to 3, what is the value of the neighbors list of the cloned node corresponding to node 1 after the first iteration of the while loop (i.e., after processing node 1)?

easy

A. A list containing cloned nodes with values [2, 3]

B. An empty list []

C. A list containing cloned nodes with values [1]

D. A list containing cloned nodes with values [3, 2]

Solution

1. Step 1: Trace the first iteration of the while loop

   Initially, queue contains node 1. We pop node 1 and iterate over its neighbors: nodes 2 and 3.

2. Step 2: Update visited and neighbors

   Nodes 2 and 3 are not visited, so they are cloned and added to visited and queue. Then, the cloned node 1's neighbors list is appended with cloned nodes 2 and 3 in order.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Neighbors of cloned node 1 after first iteration are clones of nodes 2 and 3 [OK]

Hint: Neighbors appended in order during BFS iteration [OK]

Common Mistakes:

• Assuming neighbors list is empty after first iteration
• Mixing up order of neighbors appended

2. What is the time complexity of the optimal BFS approach that starts from all land cells simultaneously in an n x n grid?

medium

A. O(n^2) for BFS plus O(n^2) for initializing the distance matrix, totaling O(n^2).

B. O(n^2) because each cell is enqueued and processed at most once.

C. O(n^3) because BFS explores neighbors for each cell multiple times.

D. O(n^4) because BFS is run from each land cell separately.

Solution

1. Step 1: Each cell is enqueued at most once because distance is updated only when -1.

   Thus, BFS processes O(n^2) cells.

2. Step 2: Each cell has up to 4 neighbors checked, so total operations are O(4*n^2) = O(n^2).

   Initialization is also O(n^2), so total complexity is O(n^2) + O(n^2) = O(n^2).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Multi-source BFS runs in linear time relative to grid size including initialization [OK]

Hint: Each cell visited once in BFS -> O(n^2) time including initialization [OK]

Common Mistakes:

• Assuming BFS runs from each land cell separately
• Counting neighbors multiple times incorrectly
• Confusing initialization cost with BFS cost

3. What is the time complexity of the optimal Kahn's Algorithm solution for the Course Schedule problem, given V courses and E prerequisite pairs?

medium

A. O(V + E) because each node and edge is processed once in BFS

B. O(V * E) due to nested loops over nodes and edges

C. O(V^2) because each node might be checked against all others

D. O(E) only, since edges dominate the processing time

Solution

1. Step 1: Identify operations on nodes and edges

   Each node is enqueued and dequeued once; each edge is visited once when decrementing in-degree.

2. Step 2: Combine to get total complexity

   Total time is proportional to number of nodes plus number of edges -> O(V + E).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Standard BFS topological sort runs in linear time relative to graph size [OK]

Hint: Each edge and node processed once -> O(V + E) [OK]

Common Mistakes:

• Assuming nested loops cause O(V*E)
• Confusing dense graph worst case with typical complexity
• Ignoring that BFS processes nodes once

4. Suppose the problem is modified so that diagonal neighbors (top-left, top-right, bottom-left, bottom-right) are also considered connected. Which of the following changes to the BFS algorithm correctly adapts to this new requirement without double counting or missing cells?

hard

A. Add diagonal neighbors to the neighbor list and keep the rest of the BFS code unchanged

B. Use DFS instead of BFS because BFS cannot handle diagonal connections

C. Keep neighbor list unchanged but run BFS twice, once for horizontal/vertical and once for diagonals

D. Add diagonal neighbors to the neighbor list and also mark visited cells immediately when enqueuing them

Solution

1. Step 1: Add diagonal neighbors to the neighbor list

   Include all 8 directions: horizontal, vertical, and diagonal neighbors.

2. Step 2: Mark cells as visited when enqueuing

   This prevents adding the same cell multiple times from different neighbors, avoiding double counting.

3. Step 3: Keep BFS traversal logic unchanged otherwise

   Running BFS twice or switching to DFS is unnecessary and inefficient.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Mark visited on enqueue avoids duplicates with expanded neighbors [OK]

Hint: Mark visited on enqueue when neighbors increase [OK]

Common Mistakes:

• Not marking visited on enqueue causing duplicates
• Running BFS multiple times unnecessarily
• Thinking BFS can't handle diagonals

5. Suppose the Surrounded Regions problem is modified so that the board can be very large and the number of 'O's connected to the boundary is small. Which of the following modifications to the BFS approach would improve space efficiency without sacrificing correctness?

hard

A. Use DFS with recursion instead of BFS to avoid storing a large queue.

B. Only enqueue boundary 'O's and avoid marking visited cells, relying on board state changes.

C. Use BFS but mark visited cells in-place and prune early when no new 'O's are found.

D. Run BFS from every 'O' cell to ensure all regions are checked independently.

Solution

1. Step 1: Consider space usage of BFS queue

   BFS queue can grow large if many 'O's are connected; marking visited in-place helps avoid revisiting.

2. Step 2: Prune BFS early when no new 'O's are found

   This reduces unnecessary queue growth and improves space efficiency without losing correctness.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   In-place marking plus pruning optimizes BFS space [OK]

Hint: In-place marking and pruning reduce BFS queue size [OK]

Common Mistakes:

• Using DFS recursion can cause stack overflow on large boards.
• Not marking visited cells causes infinite loops or revisits.
• Running BFS from every 'O' is inefficient and unnecessary.