Description Link to heading

310. Minimum Height Trees (Medium)

A tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.

Given a tree of n nodes labelled from 0 to n - 1, and an array of n - 1 edges where edges[i] = [aᵢ, bᵢ] indicates that there is an undirected edge between the two nodes aᵢ and bᵢ in the tree, you can choose any node of the tree as the root. When you select a node x as the root, the result tree has height h. Among all possible rooted trees, those with minimum height (i.e. min(h)) are called minimum height trees (MHTs).

Return a list of all MHTs$ root labels. You can return the answer in any order.

The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.

Example 1:

Input: n = 4, edges = [[1,0],[1,2],[1,3]]
Output: [1]
Explanation: As shown, the height of the tree is 1 when the root is the node with label 1 which is
the only MHT.

Example 2:

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

Constraints:

  • 1 <= n <= 2 * 10⁴
  • edges.length == n - 1
  • 0 <= aᵢ, bᵢ < n
  • aᵢ != bᵢ
  • All the pairs (aᵢ, bᵢ) are distinct.
  • The given input is guaranteed to be a tree and there will be no repeated edges.

Solution Link to heading

Initially, we designate node 0 as the root node and compute the maximum height $f$ for each subtree. Here, $f(pa)$ signifies the maximum height for the subtree rooted at node $pa$, and $f(u)$ denotes the maximum height for the subtree rooted at node $u$.

The maximum height for the subtree rooted at $u$ can be determined as the maximum among the following values:

  • The maximum height for the subtree rooted at $u$, i.e., $f(u)$. This represents the maximum height attainable in the current tree structure with $u$ pointing towards its child nodes.
  • The maximum height attainable towards the parent node $pa$, denoted as $g(u)$.
    • $g(pa) + 1$, which corresponds to the maximum height achievable in the direction from $pa$ towards its parent node.
    • $h_{pa}$, representing the maximum height achievable from $pa$ downwards (but not in the direction of $u$).
      • If $f(pa)$ is achieved in the direction from $pa$ to $u$, then $h_{pa} = f_2(pa) + 1$.
      • Otherwise, $h_{pa} = f(pa) + 1$.

Here, $f_2(pa)$ signifies the second-largest height for the subtree rooted at $pa$. Importantly, we require that the subtree associated with the second-largest height $f_2$ and the subtree corresponding to the maximum height $f$ should not share the same child node. Consequently, when calculating $f$, we must keep track of which child node of $pa$ contributes to $f(pa)$. Additionally, we need to compute $f_2$.

In cases where $pa$ has only one child node $u$, $f_2(pa)$ is set to 1, and $f(pa) = f(u) + 1$.

code Link to heading 

class Solution {
  public:
    using pii = pair<int, int>;
    pii geth(vector<vector<int>> &graph, int parent, vector<int> &max_idx, int cur, vector<pii> &heights) {
        int hmx = 1, hnd = 0; // max, second
        for (int idx : graph[cur]) {
            if (idx == parent) {
                continue;
            }
            auto [h1, h2] = geth(graph, cur, max_idx, idx, heights);
            if (h1 + 1 >= hmx) {
                hnd = hmx;
                hmx = h1 + 1;
                max_idx[cur] = idx;
            } else if (h1 + 1 >= hnd) {
                hnd = h1 + 1;
            }
        }
        heights[cur] = {hmx, hnd};
        return {hmx, hnd};
    }
    void bfs(vector<vector<int>> &graph, int parent, vector<int> &max_idx, int cur, vector<pii> &heights, vector<int> &res) {
        queue<tuple<int, int, int>> q;
        q.push({0, heights[0].first, 1});
        vector<int> vis(graph.size());
        vis[0] = 1;
        while (!q.empty()) {
            auto [idx, f_idx, g_idx] = q.front();
            res[idx] = max(res[idx], max(f_idx, g_idx));
            q.pop();
            for (int next : graph[idx]) {
                if (vis[next] == 1) {
                    continue;
                }
                vis[next] = 1;
                int gpa = 0;
                if (max_idx[idx] == next) { // 
                    gpa = heights[idx].second + 1; // 
                } else {
                    gpa = heights[idx].first + 1;
                }
                q.push({next, heights[next].first, max(g_idx + 1, gpa)});
            }
        }
    }
    vector<int> findMinHeightTrees(int n, vector<vector<int>> &edges) {
        vector<vector<int>> graph(n);
        for (auto &vec : edges) {
            graph[vec[0]].push_back(vec[1]);
            graph[vec[1]].push_back(vec[0]);
        }
        vector<pii> heights(n);
        vector<int> max_idx(n);
        geth(graph, 0, max_idx, 0, heights);
        vector<int> res(n);
        bfs(graph, 0, max_idx, 0, heights, res);
        int min_res = 1e5;
        for (int i = 0; i < n; ++i) {
            min_res = min(min_res, res[i]);
        }
        cout << endl;
        vector<int> ans;
        for (int i = 0; i < n; ++i) {
            if (res[i] == min_res) {
                ans.push_back(i);
            }
        }
        return ans;
    }
};