Graph Valid Tree

▶

Steps

setup

Check edge count for quick rejection

We first check if the number of edges equals n-1. Since edges are 4 and n-1 is 4, we proceed.

💡 A valid tree with n nodes must have exactly n-1 edges; this quick check avoids unnecessary work.

Line:

if len(edges) != n - 1:
    return False

💡 This step ensures the graph could possibly be a tree based on edge count.

setup

Build adjacency list

We build the adjacency list from the edges to represent the graph for BFS traversal.

💡 Adjacency lists allow efficient lookup of neighbors for each node during traversal.

Line:

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

💡 The graph structure is now ready for BFS neighbor exploration.

setup

Initialize BFS queue with node 0

We start BFS by enqueueing node 0 with parent -1 and mark it as in_queue.

💡 Starting BFS from node 0 explores the graph from a fixed root.

Line:

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

💡 The queue now contains the first node to process, with no parent.

traverse

Dequeue node 0 for processing

We dequeue node 0 from the queue to process its neighbors and mark it as processing.

💡 Processing node 0 means exploring its neighbors to detect cycles and add unvisited nodes.

Line:

node, parent = queue.popleft()

💡 Node 0 is now the current node being explored.

traverse

Mark node 0 as visited

We add node 0 to the visited set, confirming it has been fully processed.

💡 Marking visited prevents revisiting nodes and helps detect cycles.

Line:

if node in visited:
    return False
visited.add(node)

💡 Node 0 is now confirmed visited, no cycle detected here.

compare

Check neighbor 1 of node 0

We examine neighbor 1 of node 0. Since 1 is not the parent (-1) and not visited, we enqueue it.

💡 Neighbors not visited and not parent are candidates to explore next.

Line:

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

💡 We add neighbor 1 to the queue to explore later.

compare

Check neighbor 2 of node 0

We examine neighbor 2 of node 0. It is unvisited and not the parent, so we enqueue it.

💡 Each unvisited neighbor is added to the queue to ensure full traversal.

Line:

queue.append((neighbor, node))

💡 Node 2 will be processed after node 1.

compare

Check neighbor 3 of node 0

Neighbor 3 is unvisited and not the parent, so we enqueue it for future processing.

💡 All neighbors must be explored to ensure connectivity and detect cycles.

Line:

queue.append((neighbor, node))

💡 Node 3 will be processed after nodes 1 and 2.

traverse

Dequeue node 1 for processing

We dequeue node 1 from the queue and mark it as processing to explore its neighbors.

💡 Processing node 1 continues BFS traversal and cycle detection.

Line:

node, parent = queue.popleft()

💡 Node 1 is now the current node being explored.

traverse

Mark node 1 as visited

We add node 1 to the visited set, confirming it has been fully processed.

💡 Marking visited prevents revisiting nodes and helps detect cycles.

Line:

if node in visited:
    return False
visited.add(node)

💡 Node 1 is now confirmed visited, no cycle detected here.

compare

Check neighbor 0 of node 1 (parent)

Neighbor 0 is the parent of node 1, so we skip it to avoid false cycle detection.

💡 Skipping the parent prevents detecting the edge back to the previous node as a cycle.

Line:

if neighbor == parent:
    continue

💡 Parent edges are ignored in cycle detection.

compare

Check neighbor 4 of node 1

Neighbor 4 is unvisited and not the parent, so we enqueue it for BFS traversal.

💡 Adding unvisited neighbors ensures full graph exploration.

Line:

queue.append((neighbor, node))

💡 Node 4 will be processed after nodes 2 and 3.

traverse

Dequeue node 2 for processing

We dequeue node 2 and mark it as processing to explore its neighbors.

💡 Processing node 2 continues BFS traversal and cycle detection.

Line:

node, parent = queue.popleft()

💡 Node 2 is now the current node being explored.

traverse

Mark node 2 as visited

We add node 2 to the visited set, confirming it has been fully processed.

💡 Marking visited prevents revisiting nodes and helps detect cycles.

Line:

if node in visited:
    return False
visited.add(node)

💡 Node 2 is now confirmed visited, no cycle detected here.

compare

Check neighbor 0 of node 2 (parent)

Neighbor 0 is the parent of node 2, so we skip it to avoid false cycle detection.

💡 Skipping the parent prevents detecting the edge back to the previous node as a cycle.

Line:

if neighbor == parent:
    continue

💡 Parent edges are ignored in cycle detection.

traverse

Dequeue node 3 for processing

We dequeue node 3 and mark it as processing to explore its neighbors.

💡 Processing node 3 continues BFS traversal and cycle detection.

Line:

node, parent = queue.popleft()

💡 Node 3 is now the current node being explored.

traverse

Mark node 3 as visited

We add node 3 to the visited set, confirming it has been fully processed.

💡 Marking visited prevents revisiting nodes and helps detect cycles.

Line:

if node in visited:
    return False
visited.add(node)

💡 Node 3 is now confirmed visited, no cycle detected here.

compare

Check neighbor 0 of node 3 (parent)

Neighbor 0 is the parent of node 3, so we skip it to avoid false cycle detection.

💡 Skipping the parent prevents detecting the edge back to the previous node as a cycle.

Line:

if neighbor == parent:
    continue

💡 Parent edges are ignored in cycle detection.

traverse

Dequeue node 4 for processing

We dequeue node 4 and mark it as processing to explore its neighbors.

💡 Processing node 4 continues BFS traversal and cycle detection.

Line:

node, parent = queue.popleft()

💡 Node 4 is now the current node being explored.

traverse

Mark node 4 as visited and finish BFS

We add node 4 to visited and finish BFS as the queue is empty. No cycles were detected.

💡 All nodes reachable from 0 have been visited without cycles, indicating a valid tree.

Line:

visited.add(node)

return len(visited) == n

💡 Graph is connected and acyclic, so it is a valid tree.

from collections import defaultdict, deque

def valid_tree(n, edges):
    # STEP 1: Quick edge count check
    if len(edges) != n - 1:
        return False

    # STEP 2: Build adjacency list
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    # STEP 3: Initialize BFS queue
    visited = set()
    queue = deque([(0, -1)])

    while queue:
        # STEP 4: Dequeue node
        node, parent = queue.popleft()

        # STEP 5: Check if visited
        if node in visited:
            return False
        visited.add(node)

        # STEP 6: Explore neighbors
        for neighbor in graph[node]:
            if neighbor == parent:
                continue
            if neighbor in visited:
                return False
            queue.append((neighbor, node))

    # STEP 7: Check connectivity
    return len(visited) == n

📊

Graph Valid Tree - Watch the Algorithm Execute, Step by Step

Watching this step-by-step BFS traversal reveals how cycle detection and connectivity checks work together to confirm if the graph forms a valid tree.

Visiting: none

0

1

2

3

4

Visiting: none

0

1

2

3

4

Visiting: none

0

1

2

3

4

Queue / Stack

0

Visiting: 0

0

1

2

3

4

Visiting: 0

0

1

2

3

4

Visiting: 0

Edge: 0 → 1

0

1

2

3

4

Queue / Stack

1

Visiting: 0

Edge: 0 → 2

0

1

2

3

4

Queue / Stack

12

Visiting: 0

Edge: 0 → 3

0

1

2

3

4

Queue / Stack

123

Visiting: 1

0

1

2

3

4

Queue / Stack

23

Visiting: 1

0

1

2

3

4

Queue / Stack

23

Visiting: 1

Edge: 1 → 0

0

1

2

3

4

Queue / Stack

23

Visiting: 1

Edge: 1 → 4

0

1

2

3

4

Queue / Stack

234

Visiting: 2

0

1

2

3

4

Queue / Stack

34

Visiting: 2

0

1

2

3

4

Queue / Stack

34

Visiting: 2

Edge: 2 → 0

0

1

2

3

4

Queue / Stack

34

Visiting: 3

0

1

2

3

4

Queue / Stack

4

Visiting: 3

0

1

2

3

4

Queue / Stack

4

Visiting: 3

Edge: 3 → 0

0

1

2

3

4

Queue / Stack

4

Visiting: 4

0

1

2

3

4

Visiting: none

0

1

2

3

4

Key Takeaways

✓ A graph with n nodes must have exactly n-1 edges to be a valid tree.

This simple edge count check quickly rejects impossible cases without traversal.

✓ BFS traversal with parent tracking detects cycles by checking if a visited neighbor is not the parent.

This prevents false positives from the bidirectional edges in undirected graphs.

✓ After BFS, verifying all nodes are visited confirms the graph is connected.

Connectivity is essential for a valid tree; disconnected graphs fail this check.

Practice

1. Consider the following Python code to find the town judge:

def findJudge(n, trust):
    trust_score = [0] * (n + 1)
    for a, b in trust:
        trust_score[a] -= 1
        trust_score[b] += 1
    for i in range(1, n + 1):
        if trust_score[i] == n - 1:
            return i
    return -1

print(findJudge(3, [[1,3],[2,3]]))

What is the output of this code?

easy

A. 1

B. -1

C. 3

D. 2

Solution

1. Step 1: Trace trust_score updates

   For trust pairs [1,3] and [2,3]: trust_score[1] -= 1, trust_score[3] += 1; trust_score[2] -= 1, trust_score[3] += 1. Final trust_score = [0, -1, -1, 2].

2. Step 2: Identify judge by trust_score == n-1

   n=3, so n-1=2. Only person 3 has trust_score 2, so return 3.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Person 3 trusted by 2 others, trusts nobody [OK]

Hint: Trust score array sums trust and distrust correctly [OK]

Common Mistakes:

• Returning the person who trusts others
• Off-by-one indexing in trust_score
• Confusing trust_score values with counts

2. Consider the following buggy code snippet for the 01 Matrix problem. Which line contains the subtle bug that can cause incorrect distances or runtime errors?

medium

A. Line initializing dist with float('inf')

B. Line setting dist[i][j] = 0 when mat[i][j] == 0

C. Line with 'if i >= 0:' condition

D. Line with 'if j < n - 1:' condition in backward pass

Solution

1. Step 1: Analyze the condition 'if i >= 0:'

   This condition is always true for i in range(m), so dist[i-1][j] access is unsafe when i=0 (index -1).

2. Step 2: Identify the bug

   Accessing dist[-1][j] causes incorrect behavior or runtime error; correct condition should be 'if i > 0:'.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Boundary check off-by-one leads to invalid index [OK]

Hint: Check boundary conditions carefully to avoid invalid indices [OK]

Common Mistakes:

• Off-by-one in boundary checks
• Incorrect initialization
• Misplaced conditions

3. 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

4. What is the worst-case space complexity of the in-place DFS solution for the Number of Islands problem on an m x n grid, considering the recursion stack usage?

medium

A. O(1) -- since the grid is modified in-place, no extra space is needed.

B. O(min(m, n)) -- recursion depth limited by smaller grid dimension.

C. O(m*n) -- recursion stack can grow up to the size of the entire grid in worst case.

D. O(m + n) -- recursion stack limited by sum of rows and columns.

Solution

1. Step 1: Identify auxiliary space usage

   The grid is modified in-place, so no extra data structures are used except recursion stack.

2. Step 2: Analyze recursion stack depth

   In worst case (e.g., one large island), DFS can recurse over all cells, leading to recursion stack depth O(m*n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Recursion stack can be as large as all grid cells in worst case [OK]

Hint: Recursion stack can be as large as island size [OK]

Common Mistakes:

• Assuming constant space due to in-place modification
• Confusing recursion depth with grid dimensions

5. 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