Minimum Height Trees
A tree is an undirected graph in which any two vertices are connected by exactly one path. Find all Minimum Height Trees (MHTs) and return the roots of those MHTs. Use a graph peeling technique (BFS).
Why Interviewers Ask This
Salesforce interviewers ask this to evaluate your ability to optimize graph traversal beyond standard BFS. They specifically test if you recognize that the center of a tree minimizes height, rather than brute-forcing every node. This assesses your skill in identifying edge cases, understanding topological sorting properties, and writing efficient O(N) solutions under pressure.
How to Answer This Question
1. Clarify constraints: Confirm if the graph is connected and handle edge cases like single-node inputs immediately. 2. Visualize the problem: Explain that MHT roots are the 'centers' of the tree, meaning they minimize the maximum distance to any leaf. 3. Propose the algorithm: Introduce the topological peeling approach where you iteratively remove leaf nodes (degree 1) until one or two nodes remain. 4. Walk through logic: Detail how you initialize a queue with all leaves, decrement neighbor degrees, and add new leaves to the queue in each iteration. 5. Analyze complexity: Explicitly state that time complexity is O(V+E) since each node and edge is processed once, proving efficiency over running BFS from every node.
Key Points to Cover
- Recognizing that the solution requires finding the graph center, not just any path
- Implementing the topological sort peeling technique for O(N) efficiency
- Handling edge cases like single nodes or disconnected components correctly
- Explaining why removing leaves layer-by-layer guarantees the minimum height
- Demonstrating clear communication of the iterative reduction process
Sample Answer
To solve the Minimum Height Trees problem efficiently, I would avoid running a full BFS from every single node, as that results in O(N^2) complexity. Instead, I would use a topological peeling strategy which runs in line…
Common Mistakes to Avoid
- Running BFS from every node individually, leading to unnecessary O(N^2) time complexity
- Failing to handle the edge case where the input contains only one or two nodes
- Using DFS instead of BFS/Topological Sort, which complicates the layer-peeling logic
- Not explaining why the last remaining nodes are guaranteed to be the optimal roots
Sound confident on this question in 5 minutes
Answer once and get a 30-second AI critique of your structure, content, and delivery. First attempt is free — no signup needed.