Minimum Height Trees (Centroid by Trimming)

▶

Steps

setup

Check for single node edge case

The algorithm first checks if the tree has only one node. If so, it returns that node immediately as the centroid.

💡 This step handles the trivial case quickly, avoiding unnecessary processing.

Line:

if n == 1:
    return [0]

💡 The algorithm must handle small edge cases separately to avoid errors or inefficiency.

setup

Build adjacency list and degree array

Create an adjacency list for each node and initialize a degree array counting the number of edges per node.

💡 This representation allows efficient traversal and degree updates during leaf trimming.

Line:

graph = [[] for _ in range(n)]
degree = [0] * n
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)
    degree[u] += 1
    degree[v] += 1

💡 The degree array tracks how many neighbors each node has, which determines if a node is a leaf.

setup

Initialize leaves queue

Identify all nodes with degree 1 (leaves) and add them to the queue for processing.

💡 Leaves are the outermost nodes and will be trimmed first to find centroids.

Line:

leaves = deque([i for i in range(n) if degree[i] == 1])

💡 The initial leaves queue contains nodes 0, 2, and 3, which are the tree's outer nodes.

setup

Initialize remaining nodes count

Set the count of remaining nodes to the total number of nodes before trimming begins.

💡 Tracking remaining nodes helps determine when to stop trimming.

Line:

remaining_nodes = n

💡 Initially, all 4 nodes remain in the graph.

traverse

Start trimming leaves - iteration 1

Since more than 2 nodes remain, begin removing leaves from the queue to trim the tree.

💡 Removing leaves layer by layer shrinks the tree towards its centroid(s).

Line:

while remaining_nodes > 2:
    leaves_count = len(leaves)
    remaining_nodes -= leaves_count

💡 The first batch of leaves to remove are nodes 0, 2, and 3.

traverse

Process leaf node 0

Remove leaf node 0 from the queue and mark it as done. Update the degree of its neighbor node 1.

💡 Removing a leaf reduces its neighbor's degree, possibly creating new leaves.

Line:

leaf = leaves.popleft()
for nei in graph[leaf]:
    degree[nei] -= 1
    if degree[nei] == 1:
        leaves.append(nei)

💡 Node 1's degree decreases but remains > 1, so it is not added to leaves yet.

traverse

Process leaf node 2

Remove leaf node 2 from the queue and mark it as done. Update the degree of its neighbor node 1.

💡 Each leaf removal potentially creates new leaves by reducing neighbors' degrees.

Line:

leaf = leaves.popleft()
for nei in graph[leaf]:
    degree[nei] -= 1
    if degree[nei] == 1:
        leaves.append(nei)

💡 Node 1 becomes a leaf after this removal and will be processed next.

traverse

Process leaf node 3

Remove leaf node 3 from the queue and mark it as done. Update the degree of its neighbor node 1.

💡 Removing the last original leaf updates the neighbor's degree again.

Line:

leaf = leaves.popleft()
for nei in graph[leaf]:
    degree[nei] -= 1
    if degree[nei] == 1:
        leaves.append(nei)

💡 Node 1's degree is now 0, meaning all neighbors removed; it remains in the queue from before.

traverse

Check remaining nodes after trimming iteration 1

Update remaining nodes count after removing 3 leaves; now only 1 node remains.

💡 The loop condition will now be checked to decide if trimming continues.

Line:

remaining_nodes -= leaves_count

💡 Only node 1 remains, which is the centroid of the tree.

reconstruct

Return remaining nodes as centroids

The remaining nodes in the leaves queue are returned as the minimum height tree roots.

💡 The centroids minimize the height of the tree when chosen as roots.

Line:

return list(leaves)

💡 Node 1 is the single centroid for this tree.

from collections import deque

def findMinHeightTrees(n, edges):
    # STEP 1: Handle single node case
    if n == 1:
        return [0]

    # STEP 2: Build graph and degree array
    graph = [[] for _ in range(n)]
    degree = [0] * n
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
        degree[u] += 1
        degree[v] += 1

    # STEP 3: Initialize leaves queue
    leaves = deque([i for i in range(n) if degree[i] == 1])

    # STEP 4: Initialize remaining nodes count
    remaining_nodes = n

    # STEP 5: Trim leaves until <= 2 nodes remain
    while remaining_nodes > 2:
        leaves_count = len(leaves)
        remaining_nodes -= leaves_count
        for _ in range(leaves_count):
            leaf = leaves.popleft()
            for nei in graph[leaf]:
                degree[nei] -= 1
                if degree[nei] == 1:
                    leaves.append(nei)

    # STEP 10: Return remaining nodes as centroids
    return list(leaves)

📊

Minimum Height Trees (Centroid by Trimming) - Watch the Algorithm Execute, Step by Step

Watching the algorithm step-by-step reveals how the BFS trimming approach finds the tree's centroids by peeling off leaves iteratively, which is hard to grasp from code alone.

Visiting: none

0

1

2

3

Visiting: none

0

1

2

3

Visiting: none

0

1

2

3

Queue / Stack

023

Visiting: none

0

1

2

3

Queue / Stack

023

Visiting: none

0

1

2

3

Queue / Stack

023

Visiting: 0

Edge: 1 → 0

0

1

2

3

Queue / Stack

23

Visiting: 2

Edge: 1 → 2

0

1

2

3

Queue / Stack

31

Visiting: 3

Edge: 1 → 3

0

1

2

3

Queue / Stack

1

Visiting: none

0

1

2

3

Queue / Stack

1

Visiting: none

0

1

2

3

Queue / Stack

1

Key Takeaways

✓ The algorithm finds centroids by iteratively trimming leaves until only 1 or 2 nodes remain.

This insight is difficult to grasp from code alone because the iterative leaf removal and degree updates are subtle.

✓ The degree array is crucial for detecting leaves dynamically as the graph shrinks.

Visualizing degree changes clarifies how nodes become leaves during trimming.

✓ The queue holds the current layer of leaves, showing the BFS order of trimming from outside in.

Seeing the queue contents step-by-step reveals the order in which nodes are removed.

Practice

1. Given the following code snippet implementing topological sort positions, what is the final value of the pos array after processing conditions = [[1,2],[1,3],[3,4]] with n=4?

easy

A. [0, 0, 1, 2, 3]

B. [0, 0, 2, 1, 3]

C. [0, 0, 1, 3, 2]

D. [0, 1, 2, 3, 0]

Solution

1. Step 1: Initialize graph and in-degree arrays

   Edges: 1->2, 1->3, 3->4; in_degree: [0,0,1,1,1]

2. Step 2: Process queue and assign positions

   Queue starts with node 1 (in_degree 0). Assign pos[1]=0. Decrement in_degree of 2 and 3 to 0, enqueue both. Next, dequeue 2 (pos[2]=1), then dequeue 3 (pos[3]=2), decrement in_degree of 4 to 0, enqueue 4, assign pos[4]=3.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Positions reflect valid topological order [OK]

Hint: Track in-degree and queue order carefully [OK]

Common Mistakes:

• Swapping positions of nodes 2 and 3
• Off-by-one indexing in pos array

2. Consider the following code snippet implementing the optimal solution for the largest color value in a directed graph. Given colors = "abaca" and edges = [[0,1],[0,2],[2,3],[3,4]], what is the value of max_color_value after processing all nodes?

easy

A. 3

B. 4

C. 2

D. 5

Solution

1. Step 1: Trace dp for node 0 (color 'a')

   dp[0]['a'] = 1, max_color_value = 1

2. Step 2: Propagate to nodes 1 and 2

   Node 1 (color 'b'): dp[1]['a'] = 1, dp[1]['b'] = 1; Node 2 (color 'a'): dp[2]['a'] = 2, max_color_value = 2

3. Step 3: Propagate to node 3 (color 'c')

   dp[3]['a'] = 2, dp[3]['c'] = 1, max_color_value = 2

4. Step 4: Propagate to node 4 (color 'a')

   dp[4]['a'] = 3, max_color_value = 3

5. Final Answer:

   Option A -> Option A

6. Quick Check:

   Maximum color count along path is 3 for 'a' [OK]

Hint: Track dp updates per node carefully [OK]

Common Mistakes:

• Off-by-one in dp increments or max updates

3. What is the time complexity of the optimal approach that uses the reversed graph and Kahn's algorithm to find eventual safe states in a graph with V vertices and E edges?

medium

A. O(V + E) because each edge and vertex is processed once during graph reversal and BFS

B. O(V^2) because we process each node and its neighbors repeatedly

C. O(V * E) due to nested loops over vertices and edges

D. O(E log V) because of sorting the safe nodes at the end

Solution

1. Step 1: Analyze graph reversal and in-degree computation

   Reversing the graph and computing in-degree requires iterating over all edges once, O(E).

2. Step 2: Analyze BFS processing

   Each node is enqueued and dequeued at most once, and each edge is considered once when decrementing in-degree, total O(V + E).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Linear time in vertices and edges matches BFS and graph reversal [OK]

Hint: Each edge and vertex processed once in BFS + reversal [OK]

Common Mistakes:

• Assuming nested loops cause O(V*E)
• Confusing sorting cost as dominant
• Forgetting BFS processes each edge once

4. What is the time complexity of the optimal algorithm that uses topological sort combined with iterative DP to find the largest color value in a directed graph with n nodes and e edges?

medium

A. O(n * 26 * e) due to nested loops over edges and colors

B. O(n^2) since DP updates require comparing all pairs of nodes

C. O(n + e) ignoring the 26 colors dimension as constant

D. O((n + e) * 26) because each node and edge is processed once with 26 color updates

Solution

1. Step 1: Identify main loops

   Topological sort processes each node and edge once, so base complexity is O(n + e).

2. Step 2: Account for DP color dimension

   For each node and edge, 26 colors are updated, multiplying complexity by 26.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Complexity is O((n + e) * 26), which is linear in graph size with constant color factor [OK]

Hint: Remember DP color dimension multiplies base graph traversal [OK]

Common Mistakes:

• Ignoring 26 colors or assuming quadratic complexity

5. Examine the following buggy code snippet for sequence reconstruction using DFS postorder topological sort. Which line contains the subtle bug that can cause incorrect results when seqs is missing some elements from org?

medium

A. Line 7: Missing check if all nodes in org appear in seqs

B. Line 12: Incorrect graph edge insertion logic

C. Line 18: Incorrect cycle detection marking

D. Line 27: Missing stack reversal before comparison

Solution

1. Step 1: Identify missing validation

   The code does not check if all elements in org appear in seqs, which can cause false positives.

2. Step 2: Confirm other lines are correct

   Graph construction, cycle detection, and stack reversal are implemented correctly.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing node presence check leads to incorrect true when seqs incomplete [OK]

Hint: Always verify all org nodes appear in seqs [OK]

Common Mistakes:

• Ignoring node presence check
• Misplacing cycle detection flags