Best Roots for a Tree

Medium

You get a tree with n vertices numbered 0 to n − 1: a connected graph with no cycles, given as a list links where links[i] = [a, b] is an edge between a and b. Any vertex can be chosen as the root. The height of the rooted tree is the number of edges on the longest path from the root down to a leaf. Return every vertex that, as the root, gives the smallest possible height. The order does not matter.

Example 1

n=5, links=[[0, 1], [1, 2], [2, 3], [3, 4]] → [2]

This is the chain 0–1–2–3–4. Rooted at 2 the tree has height 2; any other root gives more.

Example 2

n=5, links=[[0, 1], [0, 2], [0, 3], [3, 4]] → [0, 3]

Rooting at 0 or at 3 gives height 2, and nothing gives less.

Example 3

n=1, links=[] → [0]

Constraints

1 ≤ n ≤ 2 · 10⁴
len(links) == n − 1
0 ≤ a, b < n, a ≠ b
No edge repeats and the graph is a tree

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Depth-First Search Breadth-First Search Graph Topological Sort

Similar problems

Module Build Order Medium Course Enrollment Queue Medium Routes That Always End Medium Longest Hike Through the Woods Medium Does This Step Come First Medium

Input

n=5, links=[[0, 1], [1, 2], [2, 3], [3, 4]]

Expected

[2]

Run checks the first 3 tests in your browser. Submit checks all 64 tests on the server, hidden ones included.