Minimum Height Trees

MediumGraphstopological sort

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given an undirected tree with n nodes labeled 0 to n - 1 as a list of n - 1 edges. If you pick any node as the root, the tree's **height** is the number of edges on the longest downward path from that root to a leaf. Return every node that, when chosen as the root, gives the **minimum possible height**. There are always one or two such nodes. You may return them in any order. Aim for O(n) time; trying every root with a BFS is too slow at the upper limit.

Examples

Input: n = 4, edges = [[1,0],[1,2],[1,3]]
Output: [1]
Rooting at node 1 gives height 1; any other root gives height 2.
Input: n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]
Output: [3,4]
Both node 3 and node 4 give height 2, which is the minimum.

Constraints

  • 1 <= n <= 2 * 10^4
  • edges.length == n - 1
  • 0 <= a, b < n and a != b
  • The edges form a valid tree

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More topological sort problems