Bird
Raised Fist0

Consider the following Python code implementing the optimal leaf trimming approach for Minimum Height Trees. Given n = 4 and edges = [[1,0],[1,2],[1,3]], what is the final returned list?

easy🧾 Code Trace Q12 of Q15
Topological Sort - Minimum Height Trees (Centroid by Trimming)
Consider the following Python code implementing the optimal leaf trimming approach for Minimum Height Trees. Given n = 4 and edges = [[1,0],[1,2],[1,3]], what is the final returned list?
A[3]
B[0, 2, 3]
C[2]
D[1]
Step-by-Step Solution
Solution:
  1. Step 1: Initialize graph and degrees

    Nodes: 0,1,2,3; edges connect 1 to 0,2,3. Degrees: 0->1, 1->3, 2->1, 3->1. Leaves initially: [0,2,3].
  2. Step 2: Trim leaves until ≤ 2 nodes remain

    Remove leaves [0,2,3], decrement neighbors' degrees. Node 1 degree reduces from 3 to 0, becomes leaf. Remaining nodes = 4 - 3 = 1. Loop ends. Return [1].
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Only node 1 remains as centroid after trimming [OK]
Quick Trick: Leaves trimmed until ≤2 nodes remain [OK]
Common Mistakes:
MISTAKES
  • Returning initial leaves
  • Off-by-one in loop
  • Not updating degrees correctly
Trap Explanation:
PITFALL
  • Confusing initial leaves with final centroids leads to wrong answer.
Interviewer Note:
CONTEXT
  • Tests ability to mentally execute BFS leaf trimming and track degrees.
Master "Minimum Height Trees (Centroid by Trimming)" in Topological Sort

3 interactive learning modes - each teaches the same concept differently

Want More Practice?

15+ quiz questions · All difficulty levels · Free

Free Signup - Practice All Questions
More Topological Sort Quizzes