You are given $n$ as the number of nodes and a 2D array of edges representing a tree having the following properties:

• It is an acyclic, undirected graph containing $n$ nodes and $n-1$ edges.

• The nodes are labeled from $0$ to $n-1$.

• An edge at the $i^{th}$ index is represented as $[a_i, b_i]$, which denotes that there is an undirected edge connecting the nodes $a_i$ and $b_i$.

Your task is to find all possible root nodes that can be used to create trees of minimum height. The height of a tree is the length of the longest path from the root node to any leaf node.

Note: The order of root nodes in the result does not matter.

Constraints

• $1 \leq n \leq 500$
• edges.length $== n - 1$
• $a_i \neq b_i$
• Each edge is unique.

So far, you have probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

A naive approach is to use Depth-first Search (DFS) to repeatedly select a node, treat it as the root of a tree, and perform DFS to calculate the height of the tree. The goal is to find the set of nodes that, when chosen as roots, result in trees with the minimum possible height.

The time complexity of this approach is $O(n^2)$, where $n$ is the number of nodes. This is because the DFS from each node takes $O(n)$ time, and we repeat this process for $n$ nodes.

The space complexity of this approach is $O(n)$, since the recursive call stack (recursive approach), or stack data structure (iterative approach) can store at most $n$ elements.

The idea is to select the central nodes of the tree as root candidates, as these nodes distribute the height as evenly as possible among the subtrees. This is because when choosing nodes from the center, we effectively divide the tree into subtrees with roughly the same number of nodes, making it more likely that the subtrees will have similar heights. Otherwise, if we choose a root node that is closer to one side of the tree, it may result in one subtree being much deeper than the other, leading to an unbalanced tree with a larger height.

To understand this concept, let’s take an example of a circle. In a circle, the diameter is the longest path from one point to another that passes through the center. Similarly, consider the tree as a circle, where the leaf nodes make up the circumference. We consider the diameter of the tree, that is, the maximum length path between two leaf nodes, where no node is repeated. The center node(s) in this diameter will be the root node(s) from which the height can be minimized.

We can safely assume that a tree can contain at most two possible central nodes that can be chosen as the root to minimize its height. To explain this, consider the diameter of a tree as a horizontal chain that can be categorized as follows:

• Odd-length chain: The middle node in this chain will be the root node that minimizes the height. This is because the length of the path from this node to the leaf node will be the minimum length path (height). No other node can be selected as the root since it will lead to a longer length path (height) to a leaf node.

• Even-length chain: The two middle nodes in this chain will be the root nodes that minimize the height. We can select two candidate nodes in this case since an even-length chain does not contain a single middle node. The length of the path from these nodes to the leaf node will be the minimum length path (height).

The slides below illustrate this concept: