Bird
Raised Fist0

What is the time complexity of the optimal leaf trimming algorithm for finding Minimum Height Trees in a tree with n nodes and n-1 edges?

medium🪤 Complexity Trap Q13 of Q15
Topological Sort - Minimum Height Trees (Centroid by Trimming)
What is the time complexity of the optimal leaf trimming algorithm for finding Minimum Height Trees in a tree with n nodes and n-1 edges?
AO(n²) because each leaf removal requires scanning all nodes.
BO(n) because each edge and node is processed at most once during trimming.
CO(n log n) due to priority queue operations for leaf selection.
DO(n + m) where m is the number of edges, which equals n-1 here.
Step-by-Step Solution
Solution:
  1. Step 1: Analyze leaf trimming operations

    Each node is added and removed from the leaves queue at most once. Each edge is visited when decrementing degrees.
  2. Step 2: Combine node and edge processing

    Since the graph is a tree, edges = n-1. Total operations proportional to n.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Linear time complexity matches leaf trimming algorithm [OK]
Quick Trick: Each node and edge processed once [OK]
Common Mistakes:
MISTAKES
  • Assuming O(n²) due to nested loops
  • Confusing with BFS from each node
  • Thinking priority queue is used
Trap Explanation:
PITFALL
  • O(n²) looks plausible if one thinks each leaf removal scans all nodes, but degrees are updated locally.
Interviewer Note:
CONTEXT
  • Checks understanding of algorithm efficiency and graph traversal costs.
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