Minimum Height Trees

NeetCode: Minimum Height Trees · LeetCode: 310. Minimum Height Trees · Difficulty: Medium

A tree is a connected undirected graph with no cycles. Given n nodes labelled 0..n-1 and n - 1 edges, you may pick any node as the root. Among all rooted trees, those with the smallest height are minimum height trees (MHTs). Return the labels of all MHT roots, in any order; the examples below print them sorted.

Example

Text

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

Brute force: BFS from every node

Rooting the tree at node r gives a height equal to the greatest BFS distance from r. Compute that for each of the n nodes, find the minimum, and return every node achieving it. The result is a List<Integer>, as LeetCode's signature requires.

Java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.List;

class Solution {
    private int heightFrom(List<List<Integer>> graph, int root) {
        int[] dist = new int[graph.size()];
        Arrays.fill(dist, -1);
        dist[root] = 0;
        Deque<Integer> queue = new ArrayDeque<>();
        queue.add(root);
        int height = 0;
        while (!queue.isEmpty()) {
            int node = queue.poll();
            height = Math.max(height, dist[node]);
            for (int next : graph.get(node)) {
                if (dist[next] == -1) {
                    dist[next] = dist[node] + 1;
                    queue.add(next);
                }
            }
        }
        return height;
    }

    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        List<Integer> result = new ArrayList<>();
        if (n == 0) {
            return result;
        }
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int[] e : edges) {
            graph.get(e[0]).add(e[1]);
            graph.get(e[1]).add(e[0]);
        }
        int[] heights = new int[n];
        int best = Integer.MAX_VALUE;
        for (int r = 0; r < n; r++) {
            heights[r] = heightFrom(graph, r);
            best = Math.min(best, heights[r]);
        }
        for (int r = 0; r < n; r++) {
            if (heights[r] == best) {
                result.add(r);
            }
        }
        return result;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.findMinHeightTrees(4, new int[][]{{1, 0}, {1, 2}, {1, 3}}));
        System.out.println(s.findMinHeightTrees(6, new int[][]{{3, 0}, {3, 1}, {3, 2}, {3, 4}, {5, 4}}));
        System.out.println(s.findMinHeightTrees(1, new int[][]{}));
        System.out.println(s.findMinHeightTrees(2, new int[][]{{0, 1}}));
    }
}

Output

[1]
[3, 4]
[0]
[0, 1]

The distances are stored in an int[] filled with -1 for "not reached yet". The loop adds roots in increasing order, so the list is already sorted. One BFS costs O(n) on a tree, and there are n of them. Time: O(n^2). Space: O(n).

Optimal: peel leaves layer by layer

The centre of a tree minimises the height, and a tree has one or two centres (the middle of its longest path). Find them by repeatedly removing all current leaves (nodes of degree 1). Each round strips one layer from the outside; when at most two nodes remain, they are the centres. Track degrees and keep the current leaves in a list. Removing a leaf decrements its neighbour's degree, and the neighbour joins the next layer when it becomes a leaf. The loop stops when remaining <= 2, and the current leaves are the answer.

For n = 6 above: the leaves are 0, 1, 2, 5; removing them leaves 3 and 4, which is remaining == 2, so the answer is [3, 4].

Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        if (n == 0) {
            return new ArrayList<>();
        }
        if (n == 1) {
            return new ArrayList<>(List.of(0));
        }
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        int[] degree = new int[n];
        for (int[] e : edges) {
            graph.get(e[0]).add(e[1]);
            graph.get(e[1]).add(e[0]);
            degree[e[0]]++;
            degree[e[1]]++;
        }
        List<Integer> leaves = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (degree[i] == 1) {
                leaves.add(i);
            }
        }
        int remaining = n;
        while (remaining > 2) {
            remaining -= leaves.size();
            List<Integer> nextLeaves = new ArrayList<>();
            for (int leaf : leaves) {
                for (int nb : graph.get(leaf)) {
                    degree[nb]--;
                    if (degree[nb] == 1) {
                        nextLeaves.add(nb);
                    }
                }
            }
            leaves = nextLeaves;
        }
        Collections.sort(leaves);
        return leaves;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.findMinHeightTrees(4, new int[][]{{1, 0}, {1, 2}, {1, 3}}));
        System.out.println(s.findMinHeightTrees(6, new int[][]{{3, 0}, {3, 1}, {3, 2}, {3, 4}, {5, 4}}));
        System.out.println(s.findMinHeightTrees(1, new int[][]{}));
        System.out.println(s.findMinHeightTrees(2, new int[][]{{0, 1}}));
    }
}

Output

[1]
[3, 4]
[0]
[0, 1]

Each edge is touched a constant number of times, and each node becomes a leaf at most once. The n == 1 case returns early because a single node has degree 0 and would never enter the leaf list. A leaf of the current layer is only visited once while more than two nodes remain, so a degree never drops below 0 in a way that adds a node twice. Time: O(n). Space: O(n).