Bird
Raised Fist0

Examine the following code snippet for finding Minimum Height Trees. Which line contains a subtle bug that causes incorrect results on single-node trees?

medium🐞 Bug Identification Q14 of Q15
Topological Sort - Minimum Height Trees (Centroid by Trimming)
Examine the following code snippet for finding Minimum Height Trees. Which line contains a subtle bug that causes incorrect results on single-node trees?
AMissing explicit check for n == 1 at the start
BLine initializing leaves with nodes of degree 1
CLine decrementing remaining_nodes by leaves_count
DLine updating degree[nei] after removing a leaf
Step-by-Step Solution
Solution:
  1. Step 1: Identify edge case handling

    The code lacks a special case for n=1, so leaves initialization is empty and the loop never runs, returning an empty list.
  2. Step 2: Understand impact of missing check

    Without returning [0] for single-node tree, the function returns incorrect empty result.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Single-node tree must be handled explicitly [OK]
Quick Trick: Check for single-node tree before main logic [OK]
Common Mistakes:
MISTAKES
  • Forgetting n=1 case
  • Incorrect leaves initialization
  • Not updating degrees properly
Trap Explanation:
PITFALL
  • Code looks correct for general cases but misses trivial single-node edge case.
Interviewer Note:
CONTEXT
  • Tests attention to edge cases and robustness of implementation.
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