How do you approach Minimum Height Trees?

The best roots are the CENTRES of the tree - the middle of its longest path. A long path has 1 centre if odd, 2 if even, which is why the answer is never larger than 2.

What is the time complexity of Minimum Height Trees?

Time complexity: O(V + E), which is O(n) in a tree.. Space complexity: O(V + E).

What are common mistakes on Minimum Height Trees?

Not detecting the cycle. If fewer nodes come out than went in there is no valid ordering, and that is usually the real question. Building the edges the wrong way round - prerequisite pairs are the classic reversal. Seeding the queue with every node instead of only those with zero indegree.

gitGood.dev

← Back to problems

Minimum Height Trees

MediumAlgorithms

Description

You are given a tree (a connected, acyclic undirected graph) with n nodes labelled 0 to n - 1 and n - 1 edges.

Rooting the tree at any node produces some height. Return all root labels that produce the minimum possible height, sorted ascending.

It can be proved there are always either one or two such roots.

Example 1

Input: n = 4, edges = [[1,0],[1,2],[1,3]]

Output: [1]

Example 2

Input: n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]

Output: [3,4]

Example 3

Input: n = 1, edges = []

Output: [0]

Constraints

- 1 <= n <= 2 * 10^4 - edges.length == n - 1 - The input is guaranteed to be a valid tree (connected, no cycles) - Trying every root is O(n^2) and too slow.

Minimum Height Trees: approach, complexity and pitfalls

A medium topological sort problem, graded against 6 test cases (3 of them hidden).

The pattern: Topological Sort

Ordering a directed acyclic graph so every dependency comes first.

Reach for it when you see: Prerequisites, build order, task scheduling, or "can this be completed?"

If you are stuck

Show the 3-step hint ladder

The best roots are the CENTRES of the tree - the middle of its longest path. A long path has 1 centre if odd, 2 if even, which is why the answer is never larger than 2.
Peel the tree like an onion: repeatedly strip all current leaves (degree 1) layer by layer. Whatever survives last is the centre.
Stop when 2 or fewer nodes remain. Handle n == 1 up front - that node has degree 0 and is never a leaf by the degree-1 test.

The optimal approach

Show the approach: Peel the leaves until the centre is all that is left

Rooting at each node and measuring the height is O(n^2) and will not pass. The structural insight: the height-minimizing roots are the centres of the tree, the midpoint(s) of its longest path (its diameter). A path with an odd number of nodes has one midpoint, an even number has two - which is exactly why the answer is always one or two nodes.

Rather than finding the diameter explicitly, peel inwards. Every node of degree 1 is a leaf and is a worst possible root, so remove the whole leaf layer at once, then recompute which nodes have become leaves and repeat. Each round strips one layer from every branch simultaneously, so the last survivors are equidistant from the extremities - the centre.

Structurally this is Kahn's algorithm on an undirected graph, with degree in place of indegree, which is why it lives in the topological-sort family despite not being a DAG problem.

Stop as soon as 2 or fewer nodes remain. The `n == 1` case needs handling first: a lone node has degree 0, never matches the degree-1 leaf test, and would otherwise be peeled to nothing.

Time: O(V + E), which is O(n) in a tree.
Space: O(V + E)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Empty input. At least one case passes an empty collection. Make sure your loop bounds and any "first element" read survive a length of zero.
Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Topological Sort mistakes

These apply to the pattern as a whole, not just this problem.

Not detecting the cycle. If fewer nodes come out than went in there is no valid ordering, and that is usually the real question.
Building the edges the wrong way round - prerequisite pairs are the classic reversal.
Seeding the queue with every node instead of only those with zero indegree.