{x}
blog image

Minimum Height Trees

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] = [ai, bi] indicates that there is an undirected edge between the two nodes ai and bi 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 * 104
  • edges.length == n - 1
  • 0 <= ai, bi < n
  • ai != bi
  • All the pairs (ai, bi) are distinct.
  • The given input is guaranteed to be a tree and there will be no repeated edges.

Solution Explanation: Minimum Height Trees

This problem aims to find all root nodes that result in minimum height trees. The solution leverages the concept of topological sorting to efficiently achieve this.

Core Idea:

The algorithm works by iteratively removing leaf nodes (nodes with only one neighbor) from the tree. This process continues until either only one or two nodes remain. The remaining nodes are the roots of the minimum height trees. This is because removing leaf nodes progressively moves towards the center of the tree.

Algorithm Steps:

  1. Handle Trivial Case: If the number of nodes (n) is 1, return [0] as the only node is the root.

  2. Build Adjacency List and Degree Array: Create an adjacency list (g) to represent the tree's structure and a degree array to store the degree (number of neighbors) of each node.

  3. Initialize Queue: Add all leaf nodes to a queue (q).

  4. Iterative Removal: While the queue is not empty, perform the following:

    • Create a temporary list ans to store the nodes to be removed in this iteration.
    • Remove nodes from the queue one by one. For each removed node:
      • Add it to ans.
      • Decrement the degree of its neighbors.
      • If a neighbor's degree becomes 1, add it to the queue (it's now a leaf).
    • After processing all nodes in the current iteration, update the ans list to hold the potential root nodes found in that round.

  5. Return Result: After the loop finishes, ans contains the root nodes of the minimum height trees.

Time and Space Complexity:

  • Time Complexity: O(V + E), where V is the number of vertices (nodes) and E is the number of edges. This is because we visit each node and edge at most once. The queue operations also take linear time.
  • Space Complexity: O(V), primarily due to the adjacency list, degree array, and queue, which all store at most V elements.

Code Examples (Python, Java, C++, Go, TypeScript):

The provided code examples in various languages effectively implement this algorithm. They all follow the same steps described above. Note the minor variations in syntax and data structures (lists, vectors, maps, etc.) depending on the specific language. The use of a deque (double-ended queue) in some solutions can further optimize queue operations.

Example Walkthrough (Python):

Let's trace the Python code for the input n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]:

  1. g will be an adjacency list representing the tree connections.
  2. degree will store degrees: [1, 1, 1, 4, 2, 1] initially.
  3. Leaf nodes (0, 1, 2, 5) are added to q.
  4. The loop iteratively removes leaf nodes, updating degrees and adding new leaf nodes to q.
  5. Finally, ans will contain [3, 4], which are the centers of the minimum height trees.

This topological sorting approach provides an efficient and elegant way to solve the Minimum Height Trees problem. The iterative removal of leaf nodes guarantees that the algorithm converges to the centers of the tree, giving us the desired root nodes.