310. Minimum Height Trees

[mah-shamim]

Topics: Depth-First Search, Breadth-First Search, Graph, Topological Sort

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.

Hint:

1. How many MHTs can a graph have at most?

[mah-shamim]

We can use the concept of graph theory to find nodes that, when chosen as roots, minimize the height of the tree. The basic idea is to perform a two-pass Breadth-First Search (BFS) to find these nodes efficiently.

Steps to Solve the Problem

1. Build the Graph: Represent the tree using an adjacency list. Each node will have a list of its connected nodes.

2. Find the Leaf Nodes: Leaf nodes are nodes with only one connection.

3. Trim the Leaves: Iteratively remove the leaf nodes and their corresponding edges from the graph until only one or two nodes remain. These remaining nodes are the potential roots for the minimum height trees.

4. Return the Result: The remaining nodes after trimming are the roots of minimum height trees.

Let's implement this solution in PHP: 310. Minimum Height Trees

<?php
/**
 * @param Integer $n
 * @param Integer[][] $edges
 * @return Integer[]
 */
function findMinHeightTrees($n, $edges) {
    if ($n == 1 || empty($edges)) {
        return [0];
    }

    $ans = [];
    $graph = [];

    // Build the adjacency list
    foreach ($edges as $edge) {
        $u = $edge[0];
        $v = $edge[1];
        $graph[$u][] = $v;
        $graph[$v][] = $u;
    }

    // Initialize leaves
    foreach ($graph as $label => $children) {
        if (count($children) == 1) {
            $ans[] = $label;
        }
    }

    // Remove leaves layer by layer
    while ($n > 2) {
        $n -= count($ans);
        $nextLeaves = [];
        foreach ($ans as $leaf) {
            $u = current($graph[$leaf]); // There is only one neighbor since it's a leaf
            // Remove the leaf from its neighbor's adjacency list
            unset($graph[$u][array_search($leaf, $graph[$u])]);
            // If neighbor becomes a leaf, add it to newLeaves
            if (count($graph[$u]) == 1) {
                $nextLeaves[] = $u;
            }
        }
        $ans = $nextLeaves;
    }

    return $ans;
}

// Example usage:
$n1 = 4;
$edges1 = [[1,0],[1,2],[1,3]];
print_r(findMinHeightTrees($n1, $edges1)); // Output: [1]

$n2 = 6;
$edges2 = [[3,0],[3,1],[3,2],[3,4],[5,4]];
print_r(findMinHeightTrees($n2, $edges2)); // Output: [3,4]
?>

Explanation:

1. Graph Construction: The adjacency list is constructed to represent the tree.

2. Initial Leaves Identification: Nodes with only one neighbor are identified as leaves.

3. Layer-by-Layer Trimming: Each layer of leaves is removed, updating the graph, and new leaves are identified until only 1 or 2 nodes are left.

4. Result: The remaining nodes are the roots that yield the minimum height trees.

This solution efficiently computes the minimum height trees in O(n) time complexity, which is suitable for large values of n up to 20,000.

[topugit]

Thanks to solve the "Minimum Height Trees" problem

[mah-shamim]

Thanks